一起动脑筋 · 先看一个小故事
机器人凑 6 元，面值有 1、3、4 元。它每次拿最大的，结果拿了 4、1、1。女孩却拿了 3、3。
把过程摊开来看
- 贪心选择先拿 4
- 剩余 2拿 1 和 1
- 共 3 枚不是最少
- 另一方案3 加 3，只要 2 枚
贪心在每一步做一个当前看起来最好的选择。
有些问题可以证明这样能得到全局最优；有些不行。这个凑钱例子说明“眼前最大”不一定让总枚数最少。
01什么是贪心？
贪心（Greedy）的基本思想是：每一步根据一个确定规则，选择当前看来最合适的方案，并继续向前。
02“当前最好”一定是选最大的吗？
不一定。
贪心规则可能是：
- 选最早结束的活动
- 选最小代价的可行边
- 选当前价值最高的某种对象
到底选什么取决于问题。
03一个直观例子：选活动
如果目标是在一间教室安排尽可能多的不重叠活动，一个经典正确贪心策略是：
每次选择“结束时间最早”的可选活动
因为它给后面的活动留下尽可能多的时间。
04为什么贪心不能只凭直觉？
有些问题中，局部最好并不能组成全局最好。
例如某些硬币面值系统中，“每次拿最大面值硬币”可能不会得到最少硬币数量。
05怎样判断一个贪心规则可能正确？
正式证明方法以后再学，但现在可以先问：
局部选择
为什么这一步不会让未来变差？
剩余问题
选完后是否还是同类问题？
能否交换
其他最优方案能否调整成包含这个选择？
06贪心和动态规划一样吗？
不一样。
贪心通常做出选择后不回头重新比较所有可能；动态规划则会系统保存和组合多个子问题结果。
后续更深入学习时会进一步比较。
你已经知道了什么
- 贪心算法每一步按规则做局部选择。
- “贪心”不等于永远选最大值。
- 局部最优不一定推出全局最优。
- 贪心算法必须建立在问题性质和正确性证明上。
- 贪心是一种算法设计思想，不是一段固定模板。
下一篇：同一道题为什么可以有不同算法？
轮到你来试一试
上图能否证明所有凑钱问题都不能用贪心？
想好了吗？点开看解释
不能。它只否定“任意面值都能用每次拿最大”。具体面值体系还需要具体分析。