挑眼前最好的

抓眼下最好的

要找零 870 元。
怎么找呢？
贪心的办法很简单。
先抓“现在能用的
最大那枚硬币”。
500 一枚，
100 三枚，
50 一枚，
10 两枚。
每回只是抓最大的，
一下子就找完了。

先点大面额硬币去抓。(870 → 500 · 100 · 100 · 100 · 50 · 10 · 10)

这就是贪心算法。
它不去权衡
往后会怎样。
只是挑“此时此刻
最好的那个”。
计算很轻，
所以决定很快。

它不看整体

贪心真正的特点是这个。
它从不摊开整张地图。
每到岔路口
只是朝“眼下看着更好的那边”
迈出一步。
因为不往远处看，
纠结少、速度快。
代价是，选过一回
就不回头。

每到岔路口点更大的数，一步步走。整张地图看不见，只在眼前两个里挑。

不看整体，
既是长处也是弱点。
快是长处。
可看不远，
眼下看着好的路，
往后也许是死胡同。
不过在有些问题上，
这个快办法
竟然刚好对。

行得通的时候

想在一间会议室里
尽量多排会。
时间不能撞。
贪心的诀窍是
先抢“最早结束的那场会”。
越早腾空，
后面就能塞进越多。
这点贪心，神奇地
给出了真正最好的答案。

先点最早结束的会去抢。撞时间的会自动落选，贪心填进最多的 4 场。

为什么这是对的答案？
挑最早结束的，
房间就最早空出来。
空时间留得最多，
那里就能塞进
最多别的会。
所以一步步贪心，
到头来整体也最好。
这类问题，贪心就是答案。

出错的反例

这回硬币古怪。
只有 1 元、3 元、4 元。
要找零 6 元。
按贪心先拿大的：
4 元一枚，再 1 元两枚。
三枚硬币。
可要是 3 元两枚呢？
两枚就搞定。
眼前的最好，
错过了整体的最好。

点两种办法对比。贪心（4·1·1 = 3 枚）和更好的路（3·3 = 2 枚）。贪心掉进了陷阱。

贪心错在哪？
它一把抓走 4 元的那刻，
剩下的 2 元就只能
用两枚 1 元来凑。
眼下这大大的一步，
毁了后面。
所以硬币普通时它对，
碰上这种错位的硬币就错。
贪心行不行，
得一题一题地查。

小结

把贪心算法看成一行，是这样的。
每一步都挑眼下看着最好的那个。
不看整体，所以又快又简单。
像找零、会议室那样，
有些问题它正是对的答案。
可碰上古怪的硬币、
绕来绕去的路，
眼前的最好就成了陷阱。
所以贪心又快又常对，
但到底对不对，得一题一题地掂量。

依次点四个要点来收尾。眼下最好 → 不看整体 → 常对 → 偶尔错。

贪心是最单纯的那种贪。
挑眼下好的，往前走。
快又轻，很有魅力，
可这单纯有时会跌进陷阱。
什么时候行、什么时候不行，
要是你抓住了这个感觉，
现在就能再添一样：
一种把一切都权衡过的、更稳重的办法。
那个，留到下次。