贪心法（Greedy Algorithm）
1. 核心思想
贪心法在每一步决策时都选择当前状态下最优的选项，并且一旦做出选择就不再回溯。它期望通过一系列局部最优选择得到全局最优解——这个期望并不总是成立，因此贪心法必须配证明。
2. 两个基本要素
2.1 贪心选择性质（Greedy Choice Property）
所求问题的整体最优解可以通过一系列局部最优的选择达到。换句话说，做第一次贪心选择时，不必考虑子问题的解，就可以断定它一定属于某个最优解。
证明方法：交换论证（exchange argument）。设原问题有一个最优解 $O$，若 $O$ 的第一步选择与贪心选择 $g$ 不同，则构造解 $O'$ 把 $O$ 中的该选择替换为 $g$，证明 $O'$ 仍是最优解（不劣于 $O$），从而说明存在包含贪心选择的最优解。
2.2 最优子结构
与动态规划相同：原问题的最优解包含子问题的最优解。
3. 贪心法 vs 动态规划
| 对比项 | 贪心法 | 动态规划 |
|---|---|---|
| 决策方式 | 每步只做一个选择，不回溯 | 枚举所有划分/选择，取最优 |
| 依赖性质 | 贪心选择性质 + 最优子结构 | 最优子结构 + 重叠子问题 |
| 计算方向 | 通常自顶向下依次决策 | 自底向上填表 |
| 复杂度 | 一般更低（常为 $O(n\log n)$） | 一般更高（常为 $O(n^2)$、$O(n^3)$） |
| 风险 | 贪心选择性质不成立时结果错误 | 状态设计正确则一定正确 |
经典反例：0-1 背包问题不能用「单位价值最高优先」的贪心法。例如容量 10，物品为 (重量 6, 价值 12)、(重量 5, 价值 9)、(重量 5, 价值 9)，单位价值最高的是第一件，贪心选它后剩余容量 4 装不下任何物品，总价值 12；而最优解是选后两件，总价值 18。背包问题（物品可分割）则可以用贪心法。
4. 典型问题
| 问题 | 贪心策略 | 复杂度 |
|---|---|---|
| 活动安排 | 按结束时间升序，能兼容就选 | $O(n\log n)$ |
| 哈夫曼编码 | 每次合并权值最小的两棵树 | $O(n\log n)$ |
| 最小生成树（Kruskal） | 按边权升序，不构成环就加入 | $O(e\log e)$ |
| 最小生成树（Prim） | 每次选连接已选集合的最小边 | $O(n^2)$ |
| 单源最短路径（Dijkstra） | 每次选未确定集合中距离最小的点 | $O(n^2)$ / $O(e\log n)$ |
| 多机调度 | 最长处理时间作业优先 | $O(n\log n)$ |
| 背包问题（可分割） | 单位价值降序装填 | $O(n\log n)$ |
| 找零钱（面值规范时） | 优先用大面值 | $O(n)$ |
5. 常见易错点
- Dijkstra 不能处理负权边：负权会破坏「已确定点的最短距离不会再变小」这一贪心前提，此时应改用 Bellman-Ford。
- 哈夫曼编码不是唯一的：存在相同权值时合并顺序可以不同，但最优编码的平均码长（WPL）唯一。
- 贪心解不唯一但最优值唯一：活动安排、最小生成树都可能存在多个不同的最优方案，代价相同。
评论