贪心选择

复习

　　前面在求最短路、最小生成树时，我们其实已经用过一种思路：每一步都选当前最好的。 这种思路有个名字——贪心（greedy）。

　　贪心的做法是：每一步都选择当前状态下看起来最优的那个选项，选完就往前走，不再回头。

　　它简单、直接、通常很快，因为没有复杂的搜索或回溯。Dijkstra 每次确定最近的节点、Kruskal 每次加最小的边，都是贪心。

　　麻烦在于：眼前最优，未必是全局最优。 贪心可能在某个局部做了“聪明”的选择，却把通向更好结果的路堵死了。

　　一个经典的例子是找零钱。如果硬币面额是 1、5、10、25，想凑出某个金额，贪心（每次尽量用大面额）往往是对的。可如果面额设计得“奇怪”一些，贪心就可能凑出更多枚硬币——正确答案需要少用大面额、多用其他组合。

　　这说明：贪心不是一种“万能方法”，而是一种需要“碰运气”的策略。 它能不能用，取决于问题本身。

　　所以，面对一个问题，贪心能不能用，要回答一个尖锐的问题：

“当前最优”的选择，会不会影响后面做出全局最优？

　　如果不会——比如选了这个最优，仍然能达到全局最优——那贪心就成立。这类问题常有一个性质：最优解包含了对当前最优的选择。 这需要证明，而不是想当然。

　　有些问题贪心确实成立（最小生成树、活动选择），有些则不成立（0/1 背包）。所以设计贪心时，最重要的不是写出代码，而是判断它到底对不对。 下一章就来看看，怎样证明或推翻一个贪心策略。

思考题 1

　　贪心策略的核心思想是什么？

思考题 2

　　为什么贪心不一定能得到全局最优？试举一个会出错的例子。

　　每一步都只考虑当前状态，选择看起来最好的那个选项，做出选择后不再回头、不做回溯。它追求的是每一步的局部最优。

　　因为局部最优未必导向全局最优。贪心的选择可能封死了通向更优解的路。比如面额设计特殊时，找零钱的贪心会用到更多硬币，而全局最优需要放弃某个大面额、采用另一种组合。

设计师 | 南国微雪