贪心法（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）唯一。
• 贪心解不唯一但最优值唯一：活动安排、最小生成树都可能存在多个不同的最优方案，代价相同。