贪心：选择性质、交换论证与反例

一句话定义

贪心（Greedy）在每一步都取「当前局部最优」选择且不回头；它并非总是正确——成立需要贪心选择性质（局部最优可进入某个全局最优解）与最优子结构，而证明的标准武器是交换论证（Exchange Argument）。

为什么重要

贪心是「最便宜的正确算法」来源：区间调度、Huffman 编码、MST、Dijkstra 内核都是贪心；但它也是「最容易写出错误算法」的思想——没有证明的贪心等于赌博。学会「先猜贪心 → 交换论证证之 → 证不出找反例转 DP」这条决策链，是算法设计能力分水岭。

前置知识

kp-002；kp-018（MST 的切割定理是现成的贪心证明样本）。

核心概念

• 贪心选择性质：存在一个最优解包含当前贪心选择，故「先做了再说」不损失最优性。
• 最优子结构：做出选择后，剩余子问题的最优解 + 该选择 = 原问题最优解。
• 交换论证模板：设 OPT 为最优解；若 OPT 与贪心首步不同，把 OPT 中的选择换成贪心选择并证明解仍可行且总代价不变差；归纳推进到贪心与 OPT 完全一致。
• 排序关键字是贪心的灵魂：区间调度按右端点、Huffman 每次合并最小两堆、jump game 按可达最远——关键字错，全盘错。
• 找零反例区：币制不规范时贪心失效（见案例），此时应转完全背包 DP。

直观类比

贪心像「每次都吃眼前最大的一口蛋糕」：如果蛋糕的切法保证「先吃大口永远不亏」（贪心选择性质），你就赢了；如果大口在后头留小口陷阱（反例），你就输了——所以先证明再动嘴。

原理与机制

区间调度（活动选择）按右端点排序的正确性证明：

贪心: 每次从可选活动中选「结束最早」者，删除与之冲突者，重复。
交换论证:
  设 OPT = {o₁, o₂, …}（按结束时间排序），G 为贪心解。
  归纳假设: 前 k 个选择中 oᵢ 与 gᵢ 相同。
  o_{k+1} 结束不早于 g_{k+1}（贪心每次取最早结束者），
  故把 OPT 中的 o_{k+1} 换成 g_{k+1} 后仍与后续活动无冲突（它结束更早）。
  ⇒ 存在最优解与 G 前 k+1 个选择一致；归纳完成。
复杂度: 排序 O(n log n) + 线性扫描 O(n)。

反例解剖：币值 {1, 3, 4} 找零 6。贪心取 4+1+1 = 3 枚，最优是 3+3 = 2 枚——「先取最大」在此不具贪心选择性质，因为 4 的选择堵死了 3+3；该场景本质是完全背包，应转 kp-026。

公式或模型

• Huffman：每次合并频率最小的两棵子树，总编码长 = Σ 频率 × 深度，可证最优（交换论证：最优树中最深兄弟必有最小两频率，交换不增代价）。
• 任务调度最小化最大延迟：按截止时间排序，T = Σ max(0, 完成时间 − 截止时间)，交换相邻逆序对可证更优——又是交换论证。
• 与 MST/最短路的关系：Kruskal 的切割定理、Dijkstra 的贪心不变量（kp-017）都是「贪心 + 领域特有不变量」的实例。

图示

区间调度: 按右端点排序后逐个取不冲突者
  时间轴 ───────────────────────▶
  a: |——|            选 a（最早结束）
  b:   |———|         与 a 冲突，弃
  c:     |——|        选 c
  d:       |———|     冲突，弃
  e:          |——|   选 e  ⇒ 共 3 个，已证最优
反例（找零 6, 币值 1,3,4）:
  贪心: 4 + 1 + 1 = 3 枚 ✗   最优: 3 + 3 = 2 枚 ✓

实例或案例

• 区间调度/会议室安排：按右端点贪心，O(n log n)。
• 跳跃游戏 II：维护「当前步可达边界/下一步边界」，BFS 层数化贪心 O(n)。
• 加油站问题：局部油量不足则起点后移，一次遍历 O(n)。
• 数据压缩：Huffman 编码是贪心的工业级应用。
• 反例集：找零（币制不规范）、0/1 背包按性价比贪心（可举出反例，须 DP）。

常见误区

• 「看起来对就交卷」：贪心题的正确率取决于证明，交换论证写不出就应怀疑。
• 排序关键字随手选（按开始时间排区间调度会错：长活动堵门）。
• 把「局部最优」当定义而忘记全局视角：贪心是策略，不是保证；保证永远来自证明。
• 能用贪心却上 DP（区间调度写成 O(n²) DP）：不是错误但是浪费，识别「贪心选择性质成立」的信号（排序关键字清晰、选择互不拖累）能省大量时间。

自测题

1. 用交换论证证明区间调度按右端点贪心最优（写出归纳的两步即可）。

答案要点：见机制节——替换不冲突 + 归纳推进。

1. 举一个「按开始时间排序」区间调度失败的反例。

答案要点：[1,100] 与 [2,3],[4,5]：按开始时间先取长区间得 1 个，最优 2 个。

1. 为什么 0/1 背包不能用「按性价比贪心」？给出反例思路。

答案要点：物品不可分割，取高性价比大件可能挤占组合空间，如容量 30，物品(25,25)(15,15)(15,15)：贪心取 25 得 25，最优 30。

与其他知识点的关系

kp-017/kp-018 是贪心的两大成熟载体；kp-026 是贪心失效时的替代方案（重叠子问题 + 无选择性质）；kp-020 的排序是多数贪心实现的第一步。

延伸阅读

《算法设计》第 4 章（含「交换论证四步法」的示范）；《算法导论》第 16.2–16.3 节（活动选择与 Huffman）。