贪心策略与正确性证明
基于通用算法套路 · 核于 2026-07
速查
- 贪心策略 = 排序键 + 选择规则：几乎所有贪心题都是「按某个键排序 + 一个 for 循环选或不选」。排序键是策略的灵魂——键选错，整个策略崩。
- 排序键怎么设计：问自己「什么样的元素应该优先被选 / 优先被排除？」。活动选择优先选结束早的（给后面留更多时间）；Huffman 优先合并频率小的（避免高频字符长编码）；分发糖果要双向扫描处理「相邻约束」。
- 常见排序键陷阱：活动选择按开始时间排序（错，开始早但拖很久的活动会挤掉多个短活动）；按时长最短排序（也错，反例可构造）；按结束时间排序才对。
- 正确性证明三方法：①交换论证（Exchange argument）——最常用，假设最优解与贪心解不同，把最优解逐步交换成贪心解且答案不变差，从而贪心解也是最优；②数学归纳法——对步数归纳「前 k 步贪心与某最优解一致」；③反证法——假设贪心解不是最优，导出矛盾。
- 交换论证模板（背下来）：设
OPT是某最优解，GREEDY是贪心解；①找到 OPT 与 GREEDY 第一个不同的选择；②用 GREEDY 的选择替换 OPT 中对应的选择，证明替换后仍是合法解且不劣化（目标函数不降）；③反复替换直至 OPT 变成 GREEDY，故 GREEDY 也是最优。 - 贪心失效判断 = 举反例：想否定一个贪心策略，构造一个小规模反例即可（如非标准币制找零、0-1 背包按单位价值）。能举出反例 ⇒ 贪心策略错 ⇒ 改排序键或上 DP。
- 贪心 vs DP 的决策树：①先想贪心策略 + 试小例；②尝试交换论证证明；③证出来了 → 用贪心（O(n log n)）；④证不出来 / 举出反例 → 用 DP（保底最优）。
- 「看起来对」≠「证明对」：贪心最危险的陷阱是策略直觉上合理就贸然用。没有证明的贪心等于在赌——面试/竞赛里没证明就写贪心，极可能挂。
- 交互演示：快速排序可视化 —— 贪心常依赖排序预处理。
一、贪心策略设计：排序键是灵魂
贪心策略的核心是回答两个问题：「按什么顺序处理元素」（排序键）和**「每个元素选还是不选」**（选择规则）。其中排序键决定了整个策略的成败。
设计排序键的方法论
问自己一个问题：「为了达成目标，什么样的元素应该优先处理？」
| 问题 | 排序键 | 直觉 |
|---|---|---|
| 活动选择（选最多不重叠） | 结束时间升序 | 结束早的给后面留更多空间 |
| 区间调度（最多不相交区间） | 结束时间升序 | 同上 |
| 分发糖果（相邻约束） | 不做单一排序，双向扫描 | 先满足「比右邻分高则糖多」再满足左邻 |
| Huffman 编码（最短带权路径） | 频率升序，优先队列 | 低频字符放深处，编码长 |
| 任务调度（最大利润） | 利润降序 + 占槽位 | 高利润任务先占靠后的截止槽 |
| 跳跃游戏（最少跳跃） | 不排序，扫最远可达 | 每步贪心扩展可达边界 |
排序键选错的典型反例
以活动选择为例，对比三种排序键：
- 按结束时间排序（正确）：
[1,3]、[2,5]、[4,6]、[6,7]→ 选[1,3]、[4,6]、[6,7]共 3 个。 - 按开始时间排序（错误）：若有一个
[1,100]的长活动排在最前，贪心先选它，会挤掉[2,5]、[4,6]、[6,7]等多个短活动，结果只剩 1 个。 - 按时长最短排序（错误）：可构造反例
[1,5]、[4,6]、[5,9]——最短是[4,6]（时长 2），先选它，但[1,5]与之冲突被排除，剩下只能选[5,9]，得 2 个；而按结束时间可得[1,5]、[5,9]也是 2 个——看似一样，换组数据[1,4]、[3,5]、[4,6]按时长选[1,4]或[4,6]都得 2 个，但能构造出按时长得 1、按结束得 2 的例子，故不可靠。
结论：排序键的正确性必须证明，不能靠「试几个例子感觉对」——下文用交换论证证明「按结束时间排序」的正确性。
二、正确性证明：交换论证
交换论证是贪心证明的最常用工具。核心思想：假设存在最优解 OPT 与贪心解 GREEDY 不同，把 OPT 逐步替换成 GREEDY 且保证每步替换后解不劣化，从而 GREEDY 也是最优。
交换论证五步模板
- 设 OPT 为某个最优解，GREEDY 为贪心解。
- 找到 OPT 与 GREEDY 第一个不同的选择。
- 用 GREEDY 的选择替换 OPT 中对应的选择，证明替换后仍合法（不违反约束）。
- 证明替换后目标函数不变差（仍最优）。
- 反复替换，OPT 最终变成 GREEDY，故 GREEDY 也是最优解。
实例：证明活动选择「按结束时间排序」正确
问题：n 个活动各有 (start, end)，选最多互不重叠（前一个 end ≤ 后一个 start）的活动。
贪心策略：按 end 升序排序，第一个（结束最早）必选，之后每个 start ≥ 上一个 end 就选。
证明（交换论证）：
- 设最优解 OPT 选了
k个活动o₁, o₂, ..., oₖ（按结束时间升序），贪心解 GREEDY 选了g₁, g₂, ..., gₘ（按结束时间升序，由排序保证g₁.end ≤ o₁.end，因为g₁是全局结束最早的）。 - 比较第一个选择：
g₁.end ≤ o₁.end（贪心选的是结束最早的活动）。 - 替换：把 OPT 中的
o₁换成g₁。因为g₁.end ≤ o₁.end ≤ o₂.start，所以g₁与o₂不冲突，替换后 OPT 仍选k个合法活动。 - 归纳：对剩下的子问题（从
g₁.end开始的活动）重复上述论证，每次贪心选择都能替换进 OPT 且不减少数量。 - 结论：GREEDY 选的活动数
m = k，即贪心解也是最优解。证毕。
其他证明方法简述
- 数学归纳法：对步数
i归纳「前 i 步贪心选择与某个最优解的前 i 步一致」。基础步（i=1）证明第一个贪心选择安全；归纳步假设前 i 步一致，证明第 i+1 步也安全。 - 反证法：假设贪心解不是最优（比最优解少），用贪心选择性质导出矛盾（如「最优解的第一步也能换成贪心选择且不变差」与「最优解已是最多」矛盾）。
实践建议：交换论证最直接、最好写，是面试/竞赛的首选。掌握「替换后仍合法 + 不劣化」这两步，绝大多数贪心证明都能搞定。
三、贪心失效判断：举反例
要否定一个贪心策略，构造一个小规模反例即可——不需要形式化证明。
找反例的思路
- 极端化：构造一个「贪心选择看似好但堵死更优方案」的输入。如长活动挤掉多个短活动、大面值硬币让总额凑不优。
- 优先怀疑「贪心选择会牺牲未来」：如果贪心选择「占用了某个稀缺资源」（时间槽、容量、位置），而更优方案需要保留这个资源——容易出反例。
- 对照已知贪心失效问题：找零（非标准币制）、0-1 背包（单位价值贪心）是经典失效例，新问题若有类似结构（选择影响后续）很可能也失效。
反例速查
| 问题 | 失效的贪心策略 | 反例 |
|---|---|---|
| 找零（币制 1/3/4，凑 6） | 每次选最大面值 | 贪心得 4+1+1=3 枚，最优 3+3=2 枚 |
| 0-1 背包（容量 50） | 按单位价值降序全装 | 贪心 160，最优 B+C=220 |
| 活动选择 | 按开始时间 / 时长排序 | 长活动挤掉多个短活动 |
决策规则：能举出反例 ⇒ 贪心策略错 ⇒ 换排序键重试，或直接上 DP。举不出反例且能交换论证 ⇒ 用贪心。
四、贪心 vs DP：怎么选
遇到最优化问题
├─ ① 先想贪心策略（排序 + for），试 2~3 个小例
├─ ② 尝试交换论证证明正确性
│ ├─ 证出来 → 用贪心（O(n log n)，快）
│ └─ 证不出来 → 继续 ③
└─ ③ 举反例 / 判断是否有「重叠子问题 + 最优子结构」
├─ 有反例 → 用 DP（保底最优）
└─ 无反例但证明困难 → 仍倾向 DP 求稳经验法则：
- 区间/调度类问题（活动选择、会议室、跳跃游戏）多优先试贪心。
- 选择影响后续容量/状态（背包、零钱、编辑）多需要 DP。
- 工程实践：贪心作为「第一尝试」，错了（反例 / WA）再上 DP——贪心写起来快，试错成本低。
五、常见贪心证明结论速查
| 问题 | 贪心策略 | 证明方法 | 是否成立 |
|---|---|---|---|
| 活动选择 / 区间调度 | 按结束时间排序 | 交换论证 | ✅ 成立 |
| Huffman 编码 | 优先队列合并最小频率 | 交换论证 + 归纳 | ✅ 成立 |
| 标准币制找零（1/5/10/25） | 每次最大面值 | 数学归纳 | ✅ 成立 |
| 非标准币制找零（1/3/4） | 每次最大面值 | 反例 6=4+1+1 | ❌ 失效 → DP |
| 0-1 背包 | 单位价值贪心 | 反例（容量 50） | ❌ 失效 → DP |
| 分数背包 | 单位价值贪心 | 交换论证 | ✅ 成立 |
| Dijkstra 最短路 | 未确定点中选最短 | 交换论证 | ✅ 成立 |
交互演示
- 快速排序可视化演示 —— 贪心策略常依赖排序预处理，理解排序是理解贪心的前置
下一步
掌握了策略设计与证明方法后，下一步进入贪心的经典模型——活动选择、跳跃游戏、分发糖果、Huffman 编码以及 Dijkstra / Prim / Kruskal 的贪心本质，见经典贪心问题。