一、贪心是什么，以及它为什么危险
贪心算法：每一步都做出当前看起来最好的选择，不回溯，不考虑全局。
它的诱人之处：实现简单、通常线性或 O(n log n)、直觉自然。
⚠️ 它的危险之处：绝大多数贪心策略是错的，而且错得不明显。 一个贪心解法可能通过 1000 个测试用例，在第 1001 个上失败。
⭐ 因此本讲的重点不是"如何想出贪心策略"，而是「如何证明它是对的」。 在算法课和面试中，一个没有证明的贪心解法等于没有解法。
两个必要条件
| 条件 | 含义 |
|---|---|
| 贪心选择性质（greedy-choice property） | 局部最优选择能导向全局最优——存在一个最优解包含这个贪心选择 |
| 最优子结构（optimal substructure） | 做出贪心选择后，剩下的子问题的最优解 + 这个选择 = 原问题的最优解 |
贪心 vs 动态规划：两者都需要最优子结构，区别在于——
DP： 考虑所有选择，取最好的 自底向上，需要子问题的解
贪心： 只考虑一个选择，不回头 自顶向下，不需要枚举
⭐ 贪心是 DP 的特例：当"最优选择可以在不看子问题解的情况下确定"时，DP 退化成贪心。
二、两种证明模板
模板一：交换论证（exchange argument）
这是最通用、最常用的贪心证明方法。
① 设 OPT 是任意一个最优解，G 是贪心解
② 找到 OPT 与 G 第一处不同的地方
③ 证明：把 OPT 在该处的选择"交换"成贪心的选择，
得到的解 OPT′ 仍然可行，且不比 OPT 差
④ 重复，最终把 OPT 变成 G，因此 G 也是最优的
⭐ 我们已经见过这个论证：第 24 讲的割性质证明就是标准的交换论证（“加一条边形成环，再删掉环上另一条边”）。
模板二：贪心保持领先（greedy stays ahead）
① 定义一个"进度"度量
② 用归纳法证明：在每一步之后，贪心解的进度都不劣于任何其他解
③ 因此最终贪心解不劣于最优解
适合"选最多的东西"这类问题。
三、活动选择（区间调度）
问题：n 个活动，第 i 个占用时间
[sᵢ, fᵢ)。选出最多的互不重叠的活动。
候选贪心策略：
| 策略 | 对吗 |
|---|---|
| 最早开始的先选 | ✗ |
| 持续时间最短的先选 | ✗ |
| 冲突最少的先选 | ✗ |
| 最早结束的先选 | ✓ |
反例（最早开始）：
A: ████████████████████████ 一个超长活动
B: ███ 三个短活动
C: ███
D: ███
最早开始 ⟹ 只选到 A（1 个）；最优是 B,C,D（3 个）
反例（最短持续）：
A: ██████
B: ███ ← 最短，但它同时挡住了 A 和 C
C: ██████
最短优先 ⟹ 只选 B（1 个）；最优是 A,C（2 个）
反例（冲突最少）：
时间 0 2 4 6 8 10 12 14
├────┤ A [0,2]
├────┤ B [4,6]
├─────┤ C [8,10]
├────┤ D [12,14]
├─────────┤ ×4 四个 [1,5]（彼此也重叠）
├─────────┤ ×4 四个 [9,13]（彼此也重叠）
├─────────┤ M [5,9]
各区间的冲突数：
A:4 B:5 C:5 D:4 [1,5]:5 [9,13]:5 M:2 ← M 严格最少
冲突最少优先 ⟹ 先选 M，而 M 同时挡掉了 B 和 C
⟹ 之后只能再选 A 和 D，共 3 个
最优（A,B,C,D） ⟹ 4 个
⭐ 这正是"局部最优消耗掉关键资源"的典型结构：M 自己看起来最无害（冲突最少），却卡在中间同时废掉两个互不冲突的活动。
type Activity struct{ Start, Finish int }
func ActivitySelection(acts []Activity) []Activity {
slices.SortFunc(acts, func(a, b Activity) int {
return cmp.Compare(a.Finish, b.Finish) // ⭐ 按结束时间排序
})
var chosen []Activity
lastFinish := math.MinInt
for _, a := range acts {
if a.Start >= lastFinish {
chosen = append(chosen, a)
lastFinish = a.Finish
}
}
return chosen
}
Θ(n log n)（排序主导）。
⭐ 正确性证明（交换论证）
设贪心第一个选的是结束最早的活动 a₁。设 OPT 是最优解，其第一个活动是 b。
- 由于 a₁ 结束最早，
f(a₁) ≤ f(b)。 - 令
OPT′ = OPT − {b} + {a₁}。因为 a₁ 比 b 结束更早，它不会与 OPT 中 b 之后的任何活动冲突，所以 OPT′ 仍然可行。 |OPT′| = |OPT|，所以 OPT′ 也是最优解，且它包含贪心的第一个选择。
这证明了贪心选择性质。剩下的是"在 a₁ 结束后的时间里选最多活动"这个同类子问题，归纳即可。∎
直觉：选结束最早的活动，为后面留下的时间最多。 一句话概括整个证明。
区间问题家族
| 问题 | 贪心策略 |
|---|---|
| 最多不重叠区间 | 按结束时间排序，能选就选 |
| 最少移除多少区间使不重叠 | n − 上一题的答案 |
| 用最少的点戳中所有区间 | 按结束时间排序，在结束点放点 |
| 最少需要几个会议室 | ⭐ 按开始时间排序 + 最小堆维护各会议室的结束时间 |
| 区间覆盖（用最少区间覆盖 [0,T]） | 每次选"能覆盖当前起点且伸得最远"的 |
⚠️ 注意"最少会议室"用的是不同策略——它不是贪心选择问题，而是"求任意时刻的最大重叠数"。用堆维护即可：
func MinMeetingRooms(acts []Activity) int {
slices.SortFunc(acts, func(a, b Activity) int { return cmp.Compare(a.Start, b.Start) })
h := &IntHeap{} // 最小堆，存各房间的结束时间
heap.Init(h)
for _, a := range acts {
if h.Len() > 0 && (*h)[0] <= a.Start {
heap.Pop(h) // 有房间空出来了，复用
}
heap.Push(h, a.Finish)
}
return h.Len()
}
四、Huffman 编码
问题：给定字符集及各字符的出现频率，构造前缀码（无码字是另一码字的前缀），使编码总长度最小。
为什么要前缀码？ 因为它可以无歧义地解码，不需要分隔符。前缀码对应一棵二叉树，字符在叶子上，路径（左 0 右 1）就是码字。
目标：最小化 Σ freq(c) × depth(c)。
贪心策略：每次合并频率最小的两个节点。
频率: a:45 b:13 c:12 d:16 e:9 f:5
① 合并 f(5) 与 e(9) → 14
② 合并 c(12) 与 b(13) → 25
③ 合并 14 与 d(16) → 30
④ 合并 25 与 30 → 55
⑤ 合并 a(45) 与 55 → 100
(100)
╱ ╲
a:45 (55)
╱ ╲
(25) (30)
╱ ╲ ╱ ╲
c:12 b:13 (14) d:16
╱ ╲
f:5 e:9
编码：a=0, c=100, b=101, f=1100, e=1101, d=111
总长度 = 45×1 + 12×3 + 13×3 + 5×4 + 9×4 + 16×3 = 224 位
定长编码需要 3 位 × 100 = 300 位 ⟹ 节省 25%
type HuffNode struct {
Freq int
Char rune
Left, Right *HuffNode
}
func BuildHuffman(freq map[rune]int) *HuffNode {
h := &nodeHeap{}
for c, f := range freq {
heap.Push(h, &HuffNode{Freq: f, Char: c})
}
for h.Len() > 1 {
a := heap.Pop(h).(*HuffNode)
b := heap.Pop(h).(*HuffNode)
heap.Push(h, &HuffNode{Freq: a.Freq + b.Freq, Left: a, Right: b})
}
return heap.Pop(h).(*HuffNode)
}
复杂度 O(n log n)（n 次堆操作）。
⭐ 最优性证明（交换论证）
引理：设 x、y 是频率最小的两个字符，则存在一棵最优前缀码树，其中 x 和 y 是深度最大的兄弟节点。
证明：设 T 是最优树，a、b 是 T 中深度最大的一对兄弟。不妨设 freq(x) ≤ freq(y)、freq(a) ≤ freq(b)。由 x、y 频率最小，freq(x) ≤ freq(a)、freq(y) ≤ freq(b)。
交换 x 与 a、y 与 b，得到 T″。代价变化：
cost(T) − cost(T″) = (freq(a) − freq(x))·(depth(a) − depth(x)) + (类似项) ≥ 0
因为 freq(a) ≥ freq(x) 且 depth(a) ≥ depth(x)（a 在最深层），两个因子都非负。所以 cost(T″) ≤ cost(T)，而 T 是最优的，故 T″ 也最优。∎
再加上最优子结构（把 x、y 合并成一个频率为 freq(x)+freq(y) 的新字符，原问题的最优解对应新问题的最优解），归纳即得 Huffman 的最优性。∎
⚠️ Huffman 只在"逐符号编码"的框架内最优。现代压缩器（zstd、brotli）用算术编码 / ANS，可以突破"每个符号至少 1 位"的限制，配合上下文建模效果远好于 Huffman。但 Huffman 仍然广泛存在于 DEFLATE（gzip、zip、PNG）和 JPEG 中，因为它解码极快。
五、背包问题：贪心的分界线
分数背包：贪心正确
物品可以切分。按"单位价值" vᵢ/wᵢ 从大到小取，取满为止。
func FractionalKnapsack(items []Item, capacity float64) float64 {
slices.SortFunc(items, func(a, b Item) int {
return cmp.Compare(b.Value/b.Weight, a.Value/a.Weight) // 单位价值降序
})
total := 0.0
for _, it := range items {
if capacity <= 0 { break }
take := math.Min(it.Weight, capacity)
total += it.Value * take / it.Weight
capacity -= take
}
return total
}
证明（交换论证）：若最优解没有取满单位价值最高的物品，就可以用它替换掉一部分单位价值较低的物品，总价值不减。∎
0-1 背包：贪心错误
物品不可切分。同样的贪心策略会失败：
容量 10
物品 A: 重 6，价值 30 单位价值 5.0
物品 B: 重 5，价值 20 单位价值 4.0
物品 C: 重 5, 价值 20 单位价值 4.0
贪心：取 A（价值 30），剩余容量 4，装不下任何东西 ⟹ 30
最优：取 B + C ⟹ 40
⭐ 为什么一个可分一个不可分就差别这么大？ 因为分数背包中"剩余容量"总能被填满，贪心选择不会浪费任何容量；而 0-1 背包中一个选择可能留下用不掉的"碎片"，局部最优的代价要到很后面才显现。
0-1 背包必须用动态规划（第 31 讲）。事实上它是 NP-难的（第 34 讲），DP 的 O(nW) 是伪多项式。
六、拟阵：贪心正确性的统一理论
有没有一个统一的判据，告诉我们什么时候贪心一定对？ 有——拟阵（matroid）。
拟阵 M = (S, I)，其中 S 是有限集，I 是 S 的子集族（称为"独立集"），满足：
- 遗传性：若 A ∈ I 且 B ⊆ A，则 B ∈ I
- 交换性质：若 A, B ∈ I 且 |A| < |B|，则存在 x ∈ B−A 使
A ∪ {x} ∈ I
定理（Rado-Edmonds）：对加权拟阵（每个元素有权重），按权重从大到小贪心选取（保持独立）总能得到最大权独立集。
例子：
| 拟阵 | S | 独立集 | 贪心算法 |
|---|---|---|---|
| 图拟阵 | 图的边集 | 不含环的边集（森林） | Kruskal（第 24 讲） |
| 均匀拟阵 | 任意集合 | 大小 ≤ k 的子集 | 取最大的 k 个 |
| 线性拟阵 | 向量组 | 线性无关组 | 高斯消元贪心 |
| 划分拟阵 | 分组的元素 | 每组至多取 kᵢ 个 | 分组贪心 |
⭐ Kruskal 的正确性可以完全不用割性质来证明——只需说明"图的森林构成一个拟阵"，然后引用 Rado-Edmonds 定理。 这是数学抽象带来威力的典型例子。
⚠️ 但拟阵不是万能的：活动选择、Huffman、Dijkstra 的贪心正确性都不能用拟阵解释（它们不是拟阵结构）。拟阵覆盖的是"选一个独立集使权重最大"这一类问题。
七、常见贪心问题速查
| 问题 | 贪心策略 | 证明方法 |
|---|---|---|
| 活动选择 | 按结束时间 | 交换论证 |
| 最少会议室 | 开始时间排序 + 堆 | 下界论证 |
| Huffman 编码 | 合并最小两个频率 | 交换论证 |
| 分数背包 | 单位价值降序 | 交换论证 |
| MST（Kruskal/Prim） | 最小边 / 最近顶点 | 割性质 / 拟阵 |
| Dijkstra | 最近的未确定顶点 | 归纳（第 25 讲） |
| 找零钱（特定币制） | 最大面额优先 | ⚠️ 对任意币制错误 |
| 任务调度最小延迟 | 按截止时间（EDF） | 交换论证 |
| 加油站问题 | 能开多远开多远 | 贪心保持领先 |
⚠️ 找零钱是最好的反面教材：美元币制 {1,5,10,25} 下贪心正确，但币制 {1, 3, 4} 下求 6 元，贪心给 4+1+1（3 枚），最优是 3+3（2 枚）。“这个贪心在我试的例子上都对"不构成证明。
八、怎么判断一个贪心是否正确
⭐ 实用检查清单：
- 能写出交换论证吗？ 写不出来，多半是错的。
- 能构造反例吗？ 花 5 分钟专门构造反例，比花 1 小时凑测试用例值得。特别注意：极端值、“大物品挡住多个小物品”、“局部最优消耗掉关键资源"这三类结构。
- 它是拟阵吗？ 是的话直接引用定理。
- 子问题会不会互相影响？ 会的话大概率要用 DP。
⭐ 一条经验：如果一个问题的贪心策略有多个"看起来都合理"的候选（如活动选择的四种策略），那么至少有三个是错的，且必须证明选中的那个。
随堂自测
- 贪心算法需要哪两个性质？它与动态规划的关系是什么？
- 写出交换论证的四个步骤。它与"贪心保持领先"各适合什么问题？
- 活动选择的四种候选策略中，为什么"最早结束"是对的？给出另外三种的反例。
- 完整证明活动选择的贪心选择性质。
- “最少会议室"为什么不能用同样的贪心？它的正确解法是什么？
- 证明 Huffman 引理：频率最小的两个字符可以放在最深的兄弟位置。
- Huffman 是最优的前缀码，为什么现代压缩器还要用算术编码？
- 分数背包贪心正确而 0-1 背包错误，本质原因是什么？给出 0-1 背包的贪心反例。
- 拟阵的两条公理是什么？说明"图的森林"满足它们，从而 Kruskal 正确。
- 币制 {1,3,4} 下求 6 元的最少硬币数，贪心给出什么？最优是什么？这说明了什么？