贪心

贪心是每步取局部最优、不回头。它快（通常 $O(n \log n)$），但正确性必须证明——局部最优不必然等于全局最优。本章讲贪心的经典成功案例、证明方法，以及失败的经典反例。

适用判断

面对最优化问题，先问：局部最优能否保证全局最优？

• 能（且有证明）→ 贪心，快；
• 不能 → 动态规划（→ 动态规划）。

贪心的结构通常比 DP 简单一层：每步只做一个选择，不比较所有子问题。代价是正确性不显然——每换一个贪心策略都要重新证明。

经典成功案例

活动选择

$n$ 个活动抢一间教室，最多能安排几个？按结束时间排序，每次选结束最早且不冲突的。交换论证可证最优。

最小生成树（Kruskal / Prim）

无向连通图求权值和最小的生成树：

• Kruskal：边按权排序，依次加入不成环的边（并查集判环，→ 并查集与字典树）——$O(E \log E)$；
• Prim：从一点出发，每次加入连接树内外的最小边（堆）——$O(E \log V)$。

正确性的核心是切割性质：任何把顶点分成两半的割，横跨割的最小边必在某棵最小生成树中。两者都是这个性质的贪心应用。

Huffman 编码

按频率给字符变长编码（高频短码），每次合并频率最小的两棵子树——最优前缀编码，$O(n \log n)$。它是压缩（gzip 的变体、JPEG）的基础，也是"贪心 + 优先队列"的样板（→ 堆与优先队列）。

正确性证明

交换论证（最常用）

证明任何最优解都能被逐步交换成贪心解而不变差：

1. 设 $O$ 是某个最优解，$G$ 是贪心解；
2. 找到两者第一个不同处，证明把 $O$ 的选择换成 $G$ 的选择（交换）不变差；
3. 归纳：$O$ 可以变成 $G$，故 $G$ 最优。

活动选择的证明是标准样板：结束最早的活动必与某最优解的第一个活动不冲突，交换后仍合法。

拟阵（matroid）

拟阵给出贪心成立的一般条件：一个带权拟阵上的贪心算法（每次选不构成环的最大权元素）必得最优基。Kruskal 的图结构是拟阵的实例，这解释了为什么"排序 + 不成环"恰好最优。多数组合问题不是拟阵，此时贪心失效、需要 DP 或近似。

失败的经典反例

0/1 背包

贪心按"单位重量价值"选取——不是最优。反例：容量 10，物品 $(w, v)$ 为 $(7, 42), (5, 25), (5, 25)$；贪心取第一个（单位价值 6）后剩 3 装不下，总价值 42；最优取两个 25，总价值 50。0/1 背包必须用 DP（或近似）。注意分数背包（物品可切分）贪心却是最优——问题的连续性改变了可解性。

找零

币制 $\{25, 10, 5, 1\}$ 贪心（每次取最大币值）恰好最优；但币制 $\{1, 3, 4\}$ 找 6：贪心给 $4+1+1$（3 枚），最优 $3+3$（2 枚）。贪心正确性依赖于具体数值结构，换一个实例就失效——所以"贪心必须证明，不能靠感觉"。

与 DP 的分界

	贪心	动态规划
每步决策	一个，不回头	比较所有子问题
正确性	需要交换论证/拟阵	最优子结构直接成立
复杂度	通常 $O(n \log n)$	通常 $O(n^2)$～$O(n^3)$
风险	反例可能很难找	状态爆炸

工程判断：先试贪心并找反例，找不到反例再证明；证明不出来就用 DP——错误的贪心比慢的 DP 危险得多。

本章要点

• 贪心每步取局部最优：快，但必须证明，不能靠感觉
• 交换论证是最常用的证明技术；拟阵给出贪心成立的一般条件（Kruskal 是实例）
• 0/1 背包与任意币制找零是经典反例：换实例即失效
• 分界判断：局部最优能否保证全局最优；能则贪心，不能则 DP