贪心算法 怎么工作

抓住眼下最好的

假设要找零 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 来补。
眼下的一大步，毁了后面。所以硬币面额普通时它是对的，像这样错开的面额就会出错。
贪心行不行得通，要每个问题分别去确认。

总结

用一句话说，贪心算法就是“每一刻都挑眼下看起来最好的”。不看全局，所以又快又简单。
像找零、排会议室这样的问题，它正好是正确答案。可遇上奇怪的硬币或弯弯绕绕的路，眼前的最好就成了陷阱。
所以贪心快、常常对，但到底对不对，要每个问题分别去掂量。

按顺序点这四个要点来总结：眼下最好 → 不看全局 → 常常对 → 偶尔错。

如果说前面看过的动态规划，是把小答案一个不漏地收集起来的谨慎办法，那么贪心就站在另一头，是最单纯的贪心：挑眼下好的，往前走。
又快又轻，很有吸引力，可正因为单纯，偶尔会掉进陷阱。
要是摸清了它什么时候行、什么时候不行，下一课就来看另一招：干脆掷骰子来选。