第7章 贪心算法——局部选择的全局效果
核心问题：为什么有时候局部最优就是全局最优，有时候却不是？
本章核心叙事
理解贪心的陷阱就是理解 LLM 的陷阱。LLM 的贪心解码（每步选最高概率 token）就是贪心算法——局部最优不保证全局最优。
这章的核心逻辑是警示性的：贪心何时有效是一个深刻的问题，拟阵理论给出了数学充分条件，但更多问题需要 DP。
章节导航
| 节 | 问题 |
|---|---|
| 7.1 贪心策略的直觉与陷阱 | 贪心每步做局部最优，但这够不够？ |
| 7.2 贪心正确性的证明 | 如何证明贪心有效？交换论证法 |
| 7.3 拟阵理论 | 贪心正确性的数学充分条件 |
| 7.4 Huffman编码 | 最优前缀编码的经典案例 |
| 7.5 分数背包 vs 0-1背包 | 同一问题，不同可处理性 |
| 7.6 贪心何时失败 | 什么时候不该用贪心 |
| 7.7 综合练习 | 三层练习设计 |
一句话核心
局部正确不等于全局正确。有时候成立，有时候不成立——知道什么时候成立才是关键。