第 14 章　贪心

本章解决的问题：每一步都挑眼前最好的那个，什么时候能保证全局最优？以及它悄悄出错的时候，为什么连个报错都没有？

14.1　贪心的适用条件

学习目标：学完本节，你能

说出贪心算法的定义，并指出它和"穷举"的本质区别；
说清贪心成立的两个前提，以及哪一个才是贪心独有的；
用一句"一条路 vs 所有路"说清贪心与动态规划的关系；
对一个新的问题判断该不该用贪心，并知道怎么验证自己的判断。

先修：13.3（Dijkstra 是一种贪心）、13.4（负权反例）。 固定术语：贪心算法（Greedy Algorithm）、最优子结构、贪心选择性质。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：只看眼前一步，凭什么能赢

先看一个日常问题：

收银员找零 63 元，手里有 50、20、10、5、1 元的纸币/硬币，怎么找张数最少？

绝大多数人的做法（不用想）：

  63 -> 先拿 50（还剩 13）
     -> 再拿 10（还剩 3）
     -> 再拿 1、1、1（还剩 0）
  一共 5 张

这个做法叫"贪心"：

贪心算法（Greedy Algorithm）：每一步都在"当前看起来最好"的选项里挑一个，选完之后不回头、不反悔。

"当前看起来最好" 就是"拿不超过剩余金额的最大面额"。这个策略不用规划、不用回溯、不用记住任何历史 —— 每一步只看眼前。

小陈第一次听说"贪心"这个术语时觉得奇怪 —— "只看眼前"听起来像一种缺点，凭什么能保证答案是对的？

这一节就回答这个问题。而且答案可能让他意外：

在本节的实测里，随机生成的 1000 种币制中，这个贪心策略只有 2.5% 能保证全对。

"只看眼前"确实是一种缺点 —— 只是我们平时用的币制恰好是那 2.5%。

二、形式化：两个前提，其中一个才是关键

一个问题能不能用贪心，取决于它是否满足两个前提。

前提一：最优子结构（Optimal Substructure）

问题的最优解，一定由"子问题的最优解"拼成。

找零问题满足它：如果"凑出 63 元的最优解"里第一个拿了 50，那剩下的 13 元也必须是"凑出 13 元的最优解" —— 否则把 13 元那段换掉，整个 63 元的解会更好，与"它是最优的"矛盾。

⚠️ 注意：这个前提【不是贪心独有的】。

动态规划（第 15 章）同样需要它 —— 它是"问题能递归求解"的基础，几乎所有算法都建立在它上面。

前提二：贪心选择性质（Greedy Choice Property）

每一步的那个"局部最优选择"，一定属于某个全局最优解。

换句话说：你不需要"回头看"—— 当前这个最优选择永远不会让你后悔。

这才是贪心独有的前提，也是它能不能用的分水岭。

找零问题满足吗？

币制	满足贪心选择性质吗
1, 5, 10, 25（美元）	✅ 满足 —— 拿最大的总是安全的
1, 3, 4（只是换了面额）	❌ 不满足 —— 下面实测给你看

同一个问题、同一份代码，换个币制就从"对"变成"错"。

与动态规划的关系：一条路 vs 所有路

这是本节最该记住的一句话：

贪心是动态规划的一个"退化特例" —— 当你确信"每个状态只需要保留一个候选"时，DP 就缩成了贪心。

用代码对照最清楚：

// 贪心：每个状态只走【一条路】
int rest = amount, count = 0;
foreach (int c in coins)              // coins 按降序
    while (rest >= c) { rest -= c; count++; }

// 动态规划：每个状态尝试【所有路】，取最好的
for (int a = 1; a <= amount; a++)
    foreach (int c in coins)
        if (c <= a && dp[a - c] + 1 < dp[a])
            dp[a] = dp[a - c] + 1;

看那个内层：

	每个状态尝试多少种选择	需要保存什么
贪心	1 种（最大的那个）	一个剩余金额变量
动态规划	所有面额	一整张表（$amount$ 个状态）

贪心快，因为它把"只有一条路"这件事当成事实。 DP 慢，因为它老老实实把每条路都试了一遍。

"哪条路是对的"就是贪心选择性质要回答的问题。

三、实测一：同一份代码，换个币制就从对变错

写一份贪心找零，先拿美元币制试：

  币制 A：1, 5, 10, 25（美元的币制）
    面额（降序）：25, 10, 5, 1

      金额    贪心枚数    最优枚数    一致
      ----    --------    --------    ----
         1           1           1    ✓
         2           2           2    ✓
         3           3           3    ✓
         4           4           4    ✓
         5           1           1    ✓
         6           2           2    ✓
         7           3           3    ✓

    1 ~ 30 共 30 个金额，贪心【全部正确】✓

然后把面额换成 1, 3, 4 —— 代码一个字没改：

  币制 B：1, 3, 4（只换了面额，代码一个字没改）
    面额（降序）：4, 3, 1

      金额    贪心枚数    最优枚数    一致
      ----    --------    --------    ----
         1           1           1    ✓
         2           2           2    ✓
         3           1           1    ✓
         4           1           1    ✓
         5           2           2    ✓
         6           3           2    ✗   <- 贪心拿的是 4 + 1 + 1
         7           2           2    ✓
        10           4           3    ✗   <- 贪心拿的是 4 + 4 + 1 + 1
        14           5           4    ✗   <- 贪心拿的是 4 + 4 + 4 + 1 + 1
        18           6           5    ✗   <- 贪心拿的是 4 + 4 + 4 + 4 + 1 + 1
        22           7           6    ✗   <- 贪心拿的是 4 + 4 + 4 + 4 + 4 + 1 + 1
        26           8           7    ✗   <- 贪心拿的是 4 + 4 + 4 + 4 + 4 + 4 + 1 + 1
        30           9           8    ✗   <- 贪心拿的是 4 + 4 + 4 + 4 + 4 + 4 + 4 + 1 + 1

    1 ~ 30 共 30 个金额，贪心有 7 个出错（第一个是 6）

把第一个出错的金额展开看：

    金额 = 6
      贪心：4 + 1 + 1  ->  3 枚
      最优：3 + 3      ->  2 枚
      贪心错在第一步：拿了 4，而最优解根本不碰 4。

这就是贪心选择性质被打破的样子：

拿 4 在"当下"看起来是最好的（它让剩余金额从 6 降到 2，一步就消掉最大的一块）， 但它堵死了后面"两个 3"这条路。

而这个错误在美元币制下永远不会发生 —— 因为 5 = 5×1、10 = 2×5、25 = 5×5， 每个面额都是更小面额的"整倍数"，所以"拿大的"永远不亏。

注意出错金额的规律（6, 10, 14, 18, 22, 26, 30）—— 从 10 开始每 4 个错一次，错在"离 4 的倍数差 2"的位置上。贪心的错误是有规律的，但规律本身也是错的。

四、实测二：随机币制里，贪心能用的只有 2.5%

一个币制对了不代表什么 —— 因为我们平时用的币制是"被人设计过的"。

如果把面额随机化呢？实测（1000 种随机币制，每种含面额 1，另加 4 个 2~30 的随机面额）：

  对每种币制，检查金额 1 ~ 200 贪心与最优解是否全部一致：

    贪心【全部正确】的币制：25 种（2.5%）
    贪心【至少错一次】的币制：975 种（97.5%）

  几个反例（面额已按降序排列）：
    币制 {12, 9, 7, 5, 1}，金额 14：贪心 3 枚，最优 2 枚
    币制 {30, 28, 23, 12, 1}，金额 35：贪心 6 枚，最优 2 枚
    币制 {28, 25, 5, 2, 1}，金额 50：贪心 6 枚，最优 2 枚

25 / 1000 —— 只有 2.5%。

这个数字值得停下来想一想：

"每次拿最大的"这个策略，在绝大多数币制下都是错的。

我们觉得它"显然对"，是因为人民币和美元的面额都被设计成了"大面额是小面额的整倍数" —— 那是货币设计的结果，不是贪心的功劳。

更要命的是第三条反例：

    币制 {28, 25, 5, 2, 1}，金额 50：贪心 6 枚，最优 2 枚

贪心要 6 枚（28 + 5 + 5 + 5 + 5 + 2），最优只要 2 枚（25 + 25） —— 差了 3 倍。

而贪心给出的答案看起来"很合理" —— 它每一步都拿了当前能拿的最大面额，你按它的思路走一遍，找不出哪里不对。

这就是贪心最危险的地方：它错了，但它错得让人看不出来。

五、实测三：贪心 vs 动态规划

把同一个问题的 DP 解法也写出来，对照着看：

  币制 B（1, 3, 4）上，任取两个金额：
    金额   6：贪心 =   3 枚，动态规划 =   2 枚，一致 = False
    金额 300：贪心 =  75 枚，动态规划 =  75 枚，一致 = True

注意第二行：金额 300 时贪心没错。

贪心的问题是"有时错"，不是"总是错" —— 而这恰恰是最危险的：它不会每次都露馅。

一个总出错的算法很快会被发现；一个 2.5% 情况下正确的算法，配上"手边这个币制刚好是对的"，就会一路通过测试、上线、直到某个用户输入了一个奇怪的金额。

再看性能（币制 200,100,50,25,10,5,1，金额 200,000，各跑 1000 次）：

    贪心      ：     1.9 ms   （结果 1000 枚）
    动态规划：   782.1 ms   （结果 1000 枚）
    动态规划是贪心的 403 倍耗时

复杂度上也对得上：

	复杂度	与金额的关系
贪心	$O(k)$，$k$ 是面额种数	无关 —— 金额涨 10 倍，耗时不变
动态规划	$O(amount \times k)$	线性 —— 金额涨 10 倍，耗时涨 10 倍

403 倍这样的差距，就是"贪心为什么值得研究"的全部理由。

但这一节的结论不是"用 DP 更保险" ——

而是：能用贪心时就用贪心，但你必须能【证明】它在这里是对的。

六、怎么确认一个贪心是对的

"证明"这件事听起来很重，实际有两条路可走。

路径一：交换论证（Exchange Argument）

这是证明贪心正确性的标准手法，模板是固定的四步：

  1. 假设存在一个最优解 O
  2. 找到 O 和贪心解 G 的【第一个不同的选择】
  3. 把 O 的那个选择换成 G 的选择，证明【结果不会变差】
  4. 反复交换，O 就被一步步改造成了 G
     -> 每一步都没变差，所以 G 也是最优点 ✓

它的直觉是："贪心的选择"和"最优解的选择"可以互换，而互换不吃亏 —— 这就是贪心选择性质的另一种说法。

14.2 节讲区间调度时会完整走一遍这四步 —— 那里会看到它实际用起来是什么样子。

路径二：小规模对拍（工程上更常用）

如果你证不出来，但想先用 —— 那就用暴力/DP 在小规模上对拍。

本节实验一、实验二做的就是这件事：

  对每种币制，检查金额 1 ~ 200 贪心与最优解是否全部一致

这是本书反复出现的手法（12.3 节的 240 组、13.2 节的 240 组、13.3 节的 225 个顶点）：

不要自己验证自己 —— 写一个思路完全不同的实现（DP、暴力枚举、Floyd-Warshall），在小规模上跑一批数据，看两者是否处处一致。

验完之后你得到的是"经验证据"，不是"证明" —— 但对工程来说，小规模全对 + 大规模抽样对，通常已经够了。

两条路径的取舍：

	交换论证	小规模对拍
给出的是	数学证明	经验证据
成本	高（要想清楚）	低（写个 DP 就行）
什么场景用	写论文、做关键系统、面试被追问"为什么对"时	日常开发、原型验证
风险	证错了自己不知道	没测到的输入仍可能出错

⚠️ 对拍的边界必须说清楚：它只能证明"这些输入上是对的"，不能证明"所有输入上都是对的"。

实验二的 2.5% 就是这个风险的量化 —— 如果当初只测了美元币制（那 30 个金额全对）， 你会得出"贪心找零是对的"这个结论，然后把它用到别的币制上。

已经有人证过的贪心，直接用

工程里真正高频的贪心，其实就那么几个 —— 它们都有现成的正确性证明：

问题	贪心策略	出处
最短路（非负权）	每次取距离最小的顶点	13.3 节 Dijkstra
拓扑排序	每次取任意一个入度为 0 的顶点	13.1 节 Kahn
区间调度	每次选结束最早的	14.2 节
Huffman 编码	每次合并频率最小的两个	14.2 节
最小生成树	每次加最短的安全边	超出本书范围

其余的贪心，默认按"没证过"处理。

七、练习

练习 14.1.1（找零的手工推演）币制 {1, 3, 4}，金额 6、10、14： (a) 手工跑一遍贪心（每次拿不超过剩余的最大面额），写出每步拿了什么。 (b) 用 DP 的思想算出最优解（提示：dp[6] = min(dp[5], dp[3], dp[2]) + 1）。 (c) 为什么 dp[6] 要看 dp[5]、dp[3]、dp[2] 这三项？

练习 14.1.2（判断）判断对错并说明理由： (a) 满足最优子结构的问题就能用贪心。 (b) 贪心每步只保留一个候选，动态规划保留多个。 (c) 只要贪心在小规模数据上全部正确，就可以放心用到生产环境。 (d) 贪心算法一定比动态规划快。

练习 14.1.3（设计一个反例）币制 {1, 6, 10}： (a) 贪心找零 12 元会怎么走？最优解是什么？ (b) 金额 18 呢？ (c) 这个币制里，贪心是"偶尔错"还是"大面积错"？

练习 14.1.4（工程判断）小陈要做一个"给用户推荐优惠券组合"的功能：用户有一张订单（金额固定），系统要从券库里选几张券叠加，使总优惠最大（每张券有面额，且有"满 X 减 Y"的门槛）。

(a) 这个问题能用"每次选面额最大的券"这个贪心吗？先别急着答 —— 说说你会怎么验证。 (b) "满减券"这个门槛的存在，破坏了哪个前提？ (c) 如果你只有一天时间上线，你会怎么做？

八、练习答案

14.1.1

(a) 贪心推演（币制 {4, 3, 1}，按降序）

金额	贪心的每一步	枚数
6	拿 4（剩 2）→ 4 太大，拿 1（剩 1）→ 拿 1（剩 0）	3 枚：`4 + 1 + 1`
10	拿 4（剩 6）→ 拿 4（剩 2）→ 拿 1（剩 1）→ 拿 1（剩 0）	4 枚：`4 + 4 + 1 + 1`
14	4（剩 10）→ 4（剩 6）→ 4（剩 2）→ 1（剩 1）→ 1（剩 0）	5 枚：`4 + 4 + 4 + 1 + 1`

(b) 最优解

金额	最优	枚数
6	`3 + 3`	2 枚
10	`3 + 3 + 4`	3 枚
14	`4 + 4 + 3 + 3`	4 枚

验证 $dp[6]$：

$$dp[6] = \min(dp[6-4], dp[6-3], dp[6-1]) + 1 = \min(dp[2], dp[3], dp[5]) + 1$$

$dp[2] = 2$（1+1）
$dp[3] = 1$（3）
$dp[5] = 2$（4+1）

$$\min(2, 1, 2) + 1 = 1 + 1 = 2$$

所以 $dp[6] = 2$ ✓ 对应"先拿 3，再拿 3"。

(c) 因为三个面额分别是 4、3、1。

$dp[6]$ 表示"凑出 6 元的最少枚数"。它的最后一步，必然是从某个更小的金额 $6-c$ 加上一枚面额 $c$ 得到的， 而 $c$ 只能是 4、3、1 中的一个 —— 所以要看 $dp[2]$、$dp[3]$、$dp[5]$ 这三项。

这正是 DP 和贪心的分界：

DP 会把三项都算出来再取最小；贪心只算 $dp[2]$（对应拿 4）那一项。

贪心"省掉"的，恰好就是那个更优的 $dp[3]$。

14.1.2

小题	判断	理由
(a)	❌ 错	最优子结构是"必要条件"不是"充分条件"。动态规划同样需要它，但 DP 不需要贪心选择性质。找零的币制 `{1,3,4}` 就满足最优子结构，但贪心是错的。
(b)	✅ 对	这就是"一条路 vs 所有路"。贪心每步只保留一个候选（拿最大的），DP 把每个状态的所有来源都算一遍再取最优。
(c)	❌ 错	小规模正确不等于全部正确。本节实验二的 2.5% 就是这个风险的量化：如果只测了几个金额，很容易误判。除非你把规模推到能覆盖所有可能的输入，否则拿到的只是经验证据。
(d)	❌ 错	复杂度上贪心通常更低（本节实测 403 倍），但如果贪心是错的，比较速度就没有意义。而且有些问题的贪心版本反而更慢（比如需要额外排序）。

(c) 是本节最该记住的一条 —— 它和 13.4 节"Bellman-Ford 在随机图上反而更快"是同一类教训： "在我测过的数据上没问题"和"没问题"之间，隔着一段距离。

14.1.3

币制 {10, 6, 1}（降序）。

(a) 金额 12：贪心拿 10 + 1 + 1（3 枚），最优是 6 + 6（2 枚）。

贪心推演：12 ≥ 10 → 拿 10（剩 2）；2 < 6 → 跳过 6；2 ≥ 1 → 拿 1（剩 1）→ 拿 1（剩 0）。3 枚。

而 6 + 6 = 12 只要 2 枚 ✗

(b) 金额 18：贪心拿 10 + 6 + 1 + 1（4 枚），最优是 6 + 6 + 6（3 枚）。

贪心：18 ≥ 10 → 拿 10（剩 8）；8 ≥ 6 → 拿 6（剩 2）；2 ≥ 1 → 拿 1、拿 1。4 枚。

最优：6 + 6 + 6 = 3 枚 ✗

(c) 大面积错 —— 凡是"离 6 的倍数差一点"的金额都会错。

规律：贪心拿了一个 10 之后，剩下的金额就不好用 6 凑了。

金额	贪心	最优	一致
6	`6`（1 枚）	`6`（1 枚）	✓
12	`10+1+1`（3 枚）	`6+6`（2 枚）	✗
18	`10+6+1+1`（4 枚）	`6+6+6`（3 枚）	✗
24	`10+10+1+1+1+1`（6 枚）	`6+6+6+6`（4 枚）	✗
30	`10+10+10`（3 枚）	`10+10+10`（3 枚）	✓

具体差多少可以用"每枚 10 损失多少"来估： 一个 10 元换成 6+1+1+1+1（5 枚）才能凑齐，所以每拿一个 10，贪心大约多花 4 枚。

这道题和实验一那个 {1,3,4} 的差别在于：{1,3,4} 错在"4 和 3 的关系"， 而 {1,6,10} 错在"10 和 6 互不整除" —— 后者错得更频繁。

14.1.4

(a) 不能直接下结论 —— 而且"每次选面额最大的"几乎肯定不对。

我会这样验证（按成本从低到高）：

步骤	做法
1. 先想清楚"最优子结构"是否成立	如果用户有三张券 A、B、C，最优组合里去掉一张，剩下的是不是"剩余券里的最优组合"？如果券的门槛互相影响，这一步就未必成立
2. 写一个暴力枚举	券的数量不多时（比如 ≤ 20 张），枚举所有子集就能拿到真值
3. 小规模对拍	随机生成一批订单和券库，贪心 vs 暴力逐一对比
4. 如果发现反例	找到第一个反例，看它错在哪个假设上

这正是本节实验一、二的做法 —— 只不过那里的"暴力"换成了 DP。

(b) "满减门槛"破坏了【贪心选择性质】。

为什么？

没有门槛时（每张券都是"直接减 Y"），总优惠就是各券面额之和 —— 那么"选面额最大的 k 张"显然是最优的，贪心选择性质成立 ✓

有了门槛之后，"选哪张券"和"当前订单金额"耦合起来了：

一张 20 元的券门槛是"满 100"，现在订单 95 元，你用了它就用不了

但如果先配一张"满 50 减 5"的券把金额降到 90，那张 20 元的券连门槛都够不着了

每一步的"最优选择"依赖于当前的金额状态，而当前金额又依赖于之前每一步的选择 —— 这就是"局部最优推不出全局最优"的典型形态。

注意：这【不影响】最优子结构（去掉最后一张券，剩下的仍然是一个同样形式的子问题）—— 破的是贪心选择性质。 这正是本节第二节强调"两个前提要分清"的原因。

(c) 一天时间，我会按这个顺序做：

优先级	做法	理由
1	先做"只选一张券"	一张券的最优 = 遍历一遍取最大，永远不会错，而且覆盖大多数场景
2	叠券先用暴力枚举（限制最多叠加 3~5 张）	组合数 $C(n,3)$ 在 $n \le 50$ 时只有 2 万，毫秒级
3	如果券很多，用 DP 做	按订单金额做状态（第 15 章的背包模型）
4	绝不先上贪心	贪心错了不会报错，只会悄悄少减几块钱 —— 用户会发现的

最后一条是关键：贪心的错误是"静默的"。

一个崩溃的 bug 一小时内就会被告警抓到；一个"少算了 3 块钱优惠"的贪心 bug，可能要等某个用户在微博上晒出对比截图才会被发现。

这就是为什么"能用贪心"和"能证明贪心能用"是两件必须分开的事。

九、常见错误

误区	纠正
认为"满足最优子结构就能用贪心"	最优子结构 DP 也需要，它是必要条件。贪心独有、且真正卡人的是【贪心选择性质】。
认为贪心"偶尔错一点，问题不大"	实测反例：币制 `{28,25,5,2,1}`、金额 50，贪心 6 枚 vs 最优 2 枚 —— 差 3 倍。而且错误是静默的，不会报错。
在少数几个输入上验过就上线	实测：随机 1000 种币制里只有 25 种（2.5%）贪心全对。只测美元币制（30 个金额全对）会得出完全错误的结论。
认为"贪心比 DP 快，所以优先用贪心"	贪心错了的话，快没有意义。正确顺序是：先确认它对，再比较速度。
把"贪心"和"启发式"混为一谈	贪心（能证明最优的）和启发式（只求近似解）是两回事。很多"看起来像贪心"的策略其实是启发式，它们不保证最优。
认为币制找零的贪心"数学上就是对的"	只对"规范币制"成立（每个面额是更小面额的整倍数）。人民币、美元恰好是，但这是一种设计，不是普遍规律。

十、本节总结

贪心算法：每一步都在"当前看起来最好"的选项里挑一个，选完不回头、不反悔。
两个前提：
- 最优子结构 —— 最优解由子问题的最优解拼成。DP 也需要它，不是贪心独有。
- 贪心选择性质 —— 局部最优选择一定属于某个全局最优解。这才是贪心独有、也真正卡人的那一条。
贪心与 DP 的关系（本节最重要的一句话）：贪心是 DP 的退化特例 —— 贪心每个状态只走一条路，DP 走所有路。 实测性能差 403 倍（1.9 ms vs 782.1 ms）。
实测一：同一份找零代码，美元币制下 30 个金额全对，换成 {1,3,4} 30 个里错 7 个（第一个是 6 元：贪心 4+1+1 三枚，最优 3+3 两枚）。
实测二（本节最有力的反预期）：随机 1000 种币制中，贪心只有 25 种（2.5%）全对。 我们觉得它"显然对"，是因为人民币/美元的面额被设计成了整倍数关系。
贪心最危险的地方：它"有时错"而不是"总是错" —— 实测金额 6 错、金额 300 对。错误是静默的，不会报错。
验证贪心的两条路径：交换论证（数学证明，14.2 节会完整走一遍四步）和小规模对拍（工程常用，但只给经验证据）。
工程原则：能用贪心时就用贪心，但你必须能证明它在这里是对的。 已经有人证过的（Dijkstra、Kahn、区间调度、Huffman）直接用；其余的默认按"没证过"处理。

下一节衔接：本节讲了"贪心要满足两个前提"，但没有真正证明过任何一个贪心是对的 —— 交换论证的四步只给了模板。

14.2 节会拿两个经典问题把这件事做实：

区间调度（"最多能参加几个不冲突的会议"）—— 完整走一遍交换论证
Huffman 编码 —— 一个"看起来完全不像贪心"的贪心

而 14.3 节会反过来：构造贪心失效的反例，并给出"该转向 DP 了"的信号。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "14.1",
  "title": "贪心的适用条件",
  "covered": [
    "贪心算法的定义：每步取当前最优、不回头不反悔",
    "两个前提的分工：最优子结构（DP 也要）vs 贪心选择性质（贪心独有）",
    "「贪心是 DP 的退化特例」：一条路 vs 所有路，含代码对照",
    "实测一：美元币制 30 个金额全对，换成 {1,3,4} 则有 7 个出错（第一个是 6 元）",
    "实测二（核心反预期）：随机 1000 种币制中贪心只有 2.5% 全对",
    "实测三：贪心与 DP 的正确性对照 + 403 倍性能差距",
    "交换论证的四步模板（为 14.2 节埋线）",
    "小规模对拍的方法与其边界（只给经验证据，不是证明）",
    "已证过的贪心清单与「其余默认没证过」的工程原则"
  ],
  "unresolved": [
    "交换论证的实际演练留到 14.2",
    "区间调度与 Huffman 编码留到 14.2",
    "0/1 背包等贪心失效反例留到 14.3",
    "动态规划的系统讲法留到第 15 章"
  ],
  "canonical_terms": {
    "贪心算法（Greedy Algorithm）": "每一步都取当前看起来最优的选项，选完不回头不反悔",
    "最优子结构（Optimal Substructure）": "问题的最优解由子问题的最优解拼成；DP 与贪心都需要",
    "贪心选择性质（Greedy Choice Property）": "每一步的局部最优选择一定属于某个全局最优解；贪心独有"
  },
  "symbols_units": {
    "k": "面额种数",
    "amount": "要找零的金额",
    "dp[a]": "凑出金额 a 所需的最少硬币数"
  },
  "assumptions": [
    "读者已掌握 13.3 的 Dijkstra（作为「贪心正确」的正例）",
    "读者理解 13.3 的负权反例（作为「贪心失效」的先声）",
    "币制的贪心结论只对「规范币制」成立，正文已明确说明"
  ],
  "word_count_actual": 3541,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch14/Sec141/",
    "实验一：美元币制 1~30 全对、{1,3,4} 有 7 个出错（第一个是 6），为实测",
    "实验二：1000 种随机币制（seed=20260918）中 25 种全对、975 种有错，为实测；对拍范围为金额 1~200",
    "实验二的三条反例、实验一的 6 元展开（4+1+1 vs 3+3）均为实测",
    "实验三：金额 6 不一致、金额 300 一致；性能 1.9ms vs 782.1ms（各跑 1000 次），为实测",
    "术语写法与 glossary.md 一致（贪心算法、最优子结构、贪心选择性质）"
  ],
  "known_issues": [
    "初版表格用「硬币展开式」（如 4 + 4 + 4 + 4 + 1 + 1）作列内容，长串把表格挤歪了 —— 改为「枚数」列 + 不一致时在行尾附展开式",
    "性能对比的币制初版写成升序 [1,5,10,...,200]，而贪心要求降序，会先拿 1 元导致结果荒谬 —— 改为降序 [200,100,...,1]",
    "初版给 TraceStr/TraceCount 加了接受 int 的「占位重载」，与真正的 List<int> 重载造成歧义且无用途 —— 已删除",
    "「贪心在随机币制下有 2.5% 全对」这个结果远低于写作预期（原以为会是 30%~60%），如实保留并写成第二节的开场钩子",
    "实验三初版只测金额 300（贪心恰好正确），容易让读者误以为贪心在 {1,3,4} 上没问题 —— 改为同时列出金额 6（错）和 300（对），并点明「贪心是有时错，不是总是错」"
  ],
  "next": "14.2 区间调度与 Huffman 编码"
}

14.1　贪心的适用条件

第 14 章　贪心

14.1　贪心的适用条件

一、直觉：只看眼前一步，凭什么能赢

二、形式化：两个前提，其中一个才是关键

前提一：最优子结构（Optimal Substructure）

前提二：贪心选择性质（Greedy Choice Property）

与动态规划的关系：一条路 vs 所有路

三、实测一：同一份代码，换个币制就从对变错

四、实测二：随机币制里，贪心能用的只有 2.5%

五、实测三：贪心 vs 动态规划

六、怎么确认一个贪心是对的

路径一：交换论证（Exchange Argument）

路径二：小规模对拍（工程上更常用）

已经有人证过的贪心，直接用

七、练习

八、练习答案

九、常见错误

十、本节总结

results matching ""

No results matching ""

第 14 章 贪心

14.1 贪心的适用条件

一、直觉：只看眼前一步，凭什么能赢

二、形式化：两个前提，其中一个才是关键

前提一：最优子结构（Optimal Substructure）

前提二：贪心选择性质（Greedy Choice Property）

与动态规划的关系：一条路 vs 所有路

三、实测一：同一份代码，换个币制就从对变错

四、实测二：随机币制里，贪心能用的只有 2.5%

五、实测三：贪心 vs 动态规划

六、怎么确认一个贪心是对的

路径一：交换论证（Exchange Argument）

路径二：小规模对拍（工程上更常用）

已经有人证过的贪心，直接用

七、练习

八、练习答案

九、常见错误

十、本节总结

results matching ""

No results matching ""

第 14 章　贪心

14.1　贪心的适用条件