算法一篇通——贪心算法

之前在写算法一篇通——动态规划时，看到不少相关的资料都谈到了贪心算法。原本我对贪心算法的认知比较简单，但是越看越混，尤其是和动态规划的差异，少有文章能说的准确透彻。因此，这几天也对贪心算法加以了解学习。

给出 n 个物体，第 i 个物体重量为 wi，要求选择尽量多的物体，使得总重量不超过 C。对于这个问题，我们很容易想到，因为在对总重量有要求的情况下要选择尽量多的物体，因此挑轻的肯定比挑重的划算。这样，我们将所有物体按重量从小到大排序，依次选择每个物体，直到装不下为止。

这就一种典型的贪心算法，只顾眼前利益，做出局部最优的选择，寄希望于这样的选择能导致全局最优解。

概念理解

贪心算法（Greedy Algorithm，又称贪婪算法），指在对问题求解时，不从整体最优上加以考虑，而总是做出在当前看来是最好的选择。也就是说，所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态只与它前面出现的状态有关，而独立于后面的状态。

贪心算法的两个性质是贪心选择性质和最优子结构性质：

• 贪心选择性质：指所求的问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择，就将所求问题简化为一个规模更小的子问题。

• 最优子结构（optimal substructure）性质：如果原问题的最优解包含的子问题的最优解，而这些子问题可以独立求解，我们就称该问题具有最优子结构性质。其包含“全局最优解包含局部最优解”的思想。

贪心算法与动态规划的区别

1. 贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。
2. 贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
3. 动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

实际上，贪心算法是一种特殊的动态规划，由于其具有贪心选择性质，保证了子问题只会被计算一次，不会被多次计算。

尽管贪心算法和动态规划都有最优子结构性质，我认为这个性质在两种算法中有着不太一样的含义：贪心的局部最优能达成全局最优，而动态规划的全局最优值中不一定全是局部最优，只是求解全局最优时要以局部最优作为基础。或者，我们可以认为，贪心算法通常都是自顶向下进行设计的，而动态规划则自顶向上。

解题思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

例题

菜鸟级

这里我选了 LeetCode 的第 122 题 Best Time to Buy and Sell Stock II。题目是这样的：给定一个数组，第 i 个元素代表第 i 天石头的买卖价。找到一种赚取最大利润的方法，你可以进行任意次交易，但是不能同时处于两笔交易中（即必须先将手上的石头卖出去才能再买）。

解答

根据贪心选择的性质，只要能赚到钱，我们就卖掉手上的石头。那么，只要后一天的价格比前一天高，我们就做买入卖出这一笔买卖。于是有代码如下：

public int maxProfit(int[] prices) {
    int total = 0;
    for (int i = 0; i < prices.length-1; i++)
        if (prices[i+1] > prices[i]) 
            total += prices[i+1]-prices[i];

    return total;
}

这样的思路是简单粗暴而有效的，但是可能需要结合多种情况考虑一下，为什么这样做是对的（我们设第 i 天的价格为 s[i]）：

• s[i] < s[i+1] < s[i+2]：这样的话，按照之前的解法，相当于省略掉中间那一笔卖出买入，只考虑第 i 天和第 i+2 天；
• s[i] > s[i+1] < s[i+2]：这样的话，我们的算法会当作没有买入过第 i 天的石头。

普通级

挑战者级

这里我选择的是 LeetCode 的第 135 题，是一道 hard 难度的题目。N 个小朋友排排坐，每个小朋友有一个分值。你需要给小朋友发糖，遵循以下规则：

• 每个小朋友保底一块糖；
• 若比左右邻居得分高，则得到的糖更多。

求最少发多少糖。

解答

需要拿一个与输入数组同样大小的数组来存储每个孩子的糖果树。

先从 0 开始向右遍历一次：第 0 个孩子先拿一块；i > 0 时，如果 ratings[i] > ratings[i-1]，那么第 i 个孩子在第 i-1 个孩子所拥有的糖果数上多拿一块，否则拿保底的一块。这一次遍历将右边的 rating 比左边大的情况全部搞定。

再从 len-1 开始向左遍历一次：第 len-1 个孩子不变，如果 ratings[i] < ratings[i-1]，那么，除非第 i-1 个孩子本身拥有的糖果数已经比多拿这一块后还要多，否则第 i－1 个孩子在第 i 个孩子所拥有的糖果数上多拿一块。这一次遍历将左边的 rating 比右边大的情况全部搞定，并且不会影响到上一次遍历所完成的工作。

因为每一次发糖都遵循贪心选择性质，最多多给一块，并且没有后效性，因此也是贪心算法的运用。

尽管时间复杂度和空间复杂度都不是最优的，但上述解法能够 AC，并且简洁易懂。当然，这个思路还是比较巧妙的，也很难短时间内想出来。

扩展

和动态规划一样，贪心算法也扩展许多衍生的问题与算法。例如，深度学习中的梯度下降算法就是贪心的。更著名的一些如下。

哈夫曼编码

我们可以用 01 编码串来代表一个字符，例如 a 为 0，c 为 00，f 为 1100。这样，可能因为其中一个字符的编码是另一个字符的前缀而导致歧义。满足任何一个编码都不是另一个的前缀的编码被称为前缀码（Prefix Code）。

这样，我们很容易想到，给定 n 个字符在文件中的出现频率 ci，求一套总长度（每个字符的频率与编码长度乘积的总和）尽量小的编码。根据一个已知结论：任何一个前缀编码都可以表示成每个非叶结点恰好有两个子结点的二叉树，我们可以通过构造一棵最优的编码树来解决这个问题。

Huffman 算法：把每个字符看作一个单结点子树放在一个树集合中，每棵子树的权值等于对应字符的频率。每次取权值最小的两棵子树合并成一棵新树，并重新放到集合中。新树的权值等于两棵子树权值之和。

从以下结论可以体现 Huffman 算法是一种贪心算法：

• 设 x 与 y 是频率最小的两个字符，则存在前缀码使得 x 和 y 具有相同码长，且仅有最后一位编码不同。这体现了贪心算法的贪心选择性质。
• 设 T 是加权字符集 C 的最优编码树，x 和 y 是树 T 中的两个叶子，且互为兄弟结点，z 是它们的父结点。若把 z 看作具有频率 f(z) = f(x) + f(y) 的字符，则树 T’ = T - {x, y} 是字符集 C’ = C - {x, y}U{z} 的一棵最优编码树。这体现了贪心算法的最优子结构性质。

Prim 算法 和 Kruskal 算法

Prim 算法 和 Kruskal 算法都是在加权无向图找到最小生成树的算法，它们也都是贪心算法。

Prim 算法：每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加 V-1 条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入树中。

Kruskal 算法：按照边的权重顺序（从小到大）处理它们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，直到树中含有 V-1 条边为止。我们从一片由 V 棵单顶点的树构成的森林开始并不断将两颗树合并（用可以找到的最短边），直到只剩下一棵树，它就是最小生成树。

如果你想要更详细地了解这部分内容，可以查看我《算法》笔记的相关章节：Algorithms-notes/笔记/4.3 最小生成树 。

启发式算法

很多的启发式算法（也叫智能算法），例如遗传算法，模拟退火算法，本质上就是贪心算法和随机化算法结合。这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更佳靠近最优解。

结语

随着第二篇算法学习的总结笔记出炉，我发现除开大二上学期《算法与数据结构》课程提到的基础而有限的算法之外，还有很多算法处于我的认知边缘之外。我准备把对这些算法的学习全部汇总到一个系列，取名为“算法一篇通”，希望写作效果能够恰如其名。

贪心算法也不简单。之后我可能还会再做一些这个方面的题，届时再进行补充。

参考资料

写作参考

• 贪心算法_百度百科
• 《算法竞赛入门经典（第 2 版）》第 8 章
• 《算法导论》第 16 章

学习参考

• 大白话解析模拟退火算法 - 苍梧 - 博客园