算法小专栏：贪心算法

本篇将介绍贪心算法相关知识。

---

一、简介

贪心算法，又称“贪婪算法”。
在对问题求解时，总是做出在当前看来是最好的选择。（局部最优解）
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。（来源360百科）

注：贪心算法是一种高性能算法，复杂度低，简单易用。
贪心算法求出来的结果不一定都是最优解。对于某些问题，它能求出最优解。而还有些问题，它能求出最优解的“近似解”。

二、算法思想

“大事化小，小事化了”。

• 大事化小：一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；

• 小事化了：从小问题找到决策的核心，确定一种局部最优解的策略。

• 通过计算出局部的最优解，来推出全局的最优解或近似解。

伪代码如下：

从问题的某一初始解出发
    while (能朝给定总目标前进一步) 
        do
            选择当前最优解作为可行解的一个解元素；
    由所有解元素组合成问题的一个可行解。

三、找零问题

这是一个求得最优解的贪心算法例子。

场景：一名收银员，需要找零88元。
怎么找零，所需要的纸/硬币的数量最少。

思路：依次找最大的纸币，
例如：找零88元，¥88 = ¥50 + ¥20 + ¥10 + ¥5 + ¥1 * 3

# arr的每一位：分别对应100块、50块、20块、10块、5块、1块纸币。
arr = [0,0,0,0,0,0]

def change(money):
    while money >= 1:
        if money >= 100:
            money -= 100
            arr[0] += 1
        elif money >= 50:
            money -= 50
            arr[1] += 1
        elif money >= 20:
            money -= 20
            arr[2] += 1
        elif money >= 10:
            money -= 10
            arr[3] += 1
        elif money >= 5:
            money -= 5
            arr[4] += 1
        elif money >= 1:
            money -= 1
            arr[5] += 1

change(88)
print arr

结果输出：

四、0-1背包问题

这是一个求得最优解的近似解的贪心算法例子。
而如果要想求得最优解，就要用到DP策略。而动态规划将在下篇介绍。

场景：一个小偷去商场偷东西，在背包称重有限下，如何拿能使得获得收益越大？（每件商品只有一个，只能选择拿与不拿）

• 贪心策略1：每次取当前能拿得下的最值钱的商品。
• 贪心策略2：每次取当前重量最轻的商品。
• 贪心策略3：每次取性价比最高的商品。（即价格/重量的值最大的商品）

接下来我们依次分析，并且找出不是最优解的反例。

贪心策略1：选取价值最大的商品。

反例：
背包最大重量 W = 4kg

商品	价格	重量
商品A	3000元	4kg
商品B	2000元	3kg
商品C	1500元	1kg

根据策略，首先选取商品A，接下来就无法再选取了，可是明明选取商品B、C更好。

贪心策略2：选取重量最轻的商品。

与策略1类似，举反例：
背包最大重量 W = 4kg

商品	价格	重量
商品A	3500元	4kg
商品B	2000元	3kg
商品C	1000元	1kg

根据策略，首先选取商品C，接下来选取商品B，可是明明选取A更好。

贪心策略3：选取性价比高的商品。

举反例：

背包最大重量 W = 4kg

商品	价格	重量
商品A	3500元	3.5kg
商品B	3000元	3kg
商品C	1000元	1kg

此时性价比相同，假设先选取商品A，则明明商品B、C更好。

注意：如果物品可以分割为任意大小，那么此时策略3可得最优解。否则，答案可能为近似解。

因此，关于0-1背包问题的最优解法——DP策略（动态规划）将在下章介绍。