找零问题
给定若干种面额，每种硬币数量不限。对于金额 n，要求使用尽可能少的硬币凑出 n。
贪心策略是：每一步选择不超过剩余金额的最大面额。这个策略是否正确，取决于面额集合，不能只根据“每次选最大面额”判断。
反例：面额 {1, 3, 4}
当目标金额为 6 时，贪心过程为：
6 → 4，剩余 2
2 → 1，剩余 1
1 → 1，剩余 0贪心解是 4 + 1 + 1，共 3 枚硬币；但最优解是 3 + 3，只需要 2 枚。因此，普通找零问题不一定具有贪心选择性质。
ANTI反例 · 局部最大不等于全局最优
面额越大并不意味着最终硬币数越少。判断贪心是否成立，必须把面额之间的组合关系也纳入分析。
面额 {25, 10, 5, 1}
对于面额 {25, 10, 5, 1}，每次选择不超过剩余金额的最大面额可以得到最少硬币数。这里先记录交换论证的关键步骤，不把它推广到任意面额集合。
| 可替换组合 | 替换结果 | 硬币数变化 |
|---|---|---|
| 5 枚 1 元 | 1 枚 5 元 | 减少 4 枚 |
| 2 枚 5 元 | 1 枚 10 元 | 减少 1 枚 |
| 3 枚 10 元 | 1 枚 25 元 + 1 枚 5 元 | 减少 1 枚 |
| 2 枚 10 元 + 1 枚 5 元 | 1 枚 25 元 | 减少 2 枚 |
这些交换说明：如果一个方案包含上述组合，就不可能是最优方案，因为替换后金额不变但硬币更少。正式证明还需要补充“规范化后的表示与贪心表示一致”的论证。
活动选择与区间调度
活动选择问题需要从一组有开始时间和结束时间的活动中，选出最多个互不冲突的活动。经典贪心规则是：每次选择结束时间最早、且与已选活动不冲突的活动。
这个规则的正确性通常使用交换论证证明，详见正确性证明。
分数背包与 0-1 背包
分数背包允许切割物品，因此可以按照单位价值从高到低装入。0-1 背包不允许切割物品，即使某件物品的单位价值最高，也可能因为占据容量而使整体方案变差。
这两个问题的相似外表很容易造成误用，是区分贪心和动态规划的重要例子。
Huffman 编码与合并问题
Huffman 编码反复从当前集合中取出权重最小的两个节点，合并后再放回集合。优先队列可以高效实现这一过程。
合并果子等问题也采用类似的“每次合并当前最小的两个对象”的策略，但仍需要根据具体目标证明该规则正确。
图算法中的贪心
Kruskal 和 Prim 讨论的是无向、带权图上的最小生成树问题，并要求图连通；如果图不连通，Kruskal 得到的是最小生成森林，而 Prim 需要从每个连通分量分别启动。Dijkstra 讨论的是有向或无向带权图上的单源最短路径问题，并要求所有边权非负。
- Kruskal 按边权升序尝试选边，并用并查集避免成环；在连通图上最终得到最小生成树；
- Prim 每次选择连接当前生成树与树外顶点的最小权边；在连通图上逐步扩展出最小生成树；
- Dijkstra 每次确定当前距离最小的未确定顶点，但要求所有边权非负。
它们都使用了贪心思想，但正确性依据不同，不能只因为“每次选最小”就把它们视为同一个算法。
使用条件不能省略
“这是一个排序问题”“这是一个图问题”都不能直接推出贪心正确。写算法时必须同时写出输入约束、可行性条件和正确性证明所依赖的前提。
练习
- 对面额
{1, 3, 4}和金额6，分别写出贪心解和最优解。 - 为活动选择问题写出贪心选择规则，并尝试用交换论证证明它的正确性。
- 解释为什么分数背包可以使用单位价值贪心，而 0-1 背包通常不能。
- 说明 Huffman 编码为什么需要优先队列。