14.3　贪心失效的反例

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

• 构造 0/1 背包的贪心反例，并说清它错在哪一步；
• 解释什么叫"近似比无界"，以及它为什么比"偶尔错一次"严重得多；
• 说清 "允许切分"这一个字的改动为什么让同一个贪心从"无界偏差"变成"精确最优"；
• 用四类信号快速判断一个问题是"能用贪心"还是"该转向动态规划"。

先修：14.1（两个前提、静默的错误）、14.2（交换论证）。 固定术语：贪心算法、贪心选择性质、最优子结构、0/1 背包、分数背包。 环境与版本：.NET 8 / C# 12。 预计阅读：28 分钟。

一、直觉：只改一个字，贪心就崩了

14.1 和 14.2 各有一个主题：

这一节把"失败"这一侧补完 —— 而且是最经典、最有教学价值的那一个：

背包问题：一个容量固定的背包，一堆有重量、有价值的物品，怎么装总价值最大？

只差一个字，分成两个版本：

• 分数背包：物品可以切开来拿（"拿这袋米的 3/5"）
• 0/1 背包：要么整个拿走，要么不拿

两个版本用的是同一个贪心策略：按"单位价值"（价值 ÷ 重量）从高到低拿。

结果：

小陈第一次看到这个对照时的反应是："就改一个字？"

是的，就一个字。而这个字改变的是：一个物品到底是"连续可分的资源"，还是"全有或全无的决策"。

二、0/1 背包的反例

(A) 一个具体的例子

      容量 = 10
      物品 A：重  6，价值 30（单位价值 5.0）
      物品 B：重  5，价值 20（单位价值 4.0）
      物品 C：重  5，价值 20（单位价值 4.0）

      贪心（按单位价值）：先拿 A（重 6），剩余容量 4，B 和 C 都装不下 -> 总价值 30
      最优：B + C（重 5+5=10，刚好装满）-> 总价值 40
      贪心只拿到最优的 75.0%

看贪心错在哪一步：它拿了 A，因为 A 的单位价值最高（5.0 > 4.0） —— 从"每一单位容量能换多少价值"来看，这个选择完全正确。

但它没算到：拿了 A 之后剩下的 4 格容量，什么也装不下 —— 而那两个"单位价值低一点"的物品，合起来恰好能把 10 格填满。

这就是 14.1 说的"贪心选择性质不成立"的具体形态：

"当前单位价值最高"这个局部判断，在这里不属于任何全局最优解 —— 因为它的价值是"每一格"衡量的，而它的代价是"一整块容量"支付的。

(B) 更糟的是：差距可以任意大

上面那个例子差 25%。但真正的问题不是"差多少"，而是"有没有上界"。实测：

      构造：容量 W，只放两个物品
        物品 A：重 1，价值 2      （单位价值 2.0）
        物品 B：重 W，价值 W      （单位价值 1.0）

      W          贪心                最优                比值
      ---------  ------------------  ------------------  ----------
      100           2（拿 A 就满了）            100（拿 B）        50.0 倍
      1,000         2（拿 A 就满了）          1,000（拿 B）       500.0 倍
      10,000        2（拿 A 就满了）         10,000（拿 B）      5000.0 倍
      100,000       2（拿 A 就满了）        100,000（拿 B）     50000.0 倍

比值 = $W/2$ —— 它随 $W$ 无限增长。

这在算法里叫「近似比无界」：0/1 背包的贪心，不存在"最多差百分之多少"的保证。

这个性质比"偶尔错一次"严重得多：一个"最多差 5%"的算法，工程上可以直接用； 一个"可能差 5 万倍"的算法，连兜底都做不了。

注意这个构造有多简单：只有两个物品。

贪心看到一个"单位价值 2.0、重量只有 1"的小东西，和一个"单位价值 1.0、重量是 W"的大东西 —— 它毫不犹豫地拿了小的，然后发现背包满了。

三、实测：随机实例上，贪心到底有多准？

反例说明"会错"，那么"错得频繁吗"？上对拍：

  1000 个随机实例（每组 6~15 个物品，容量 10~40）：

    贪心恰好等于最优的：699 / 1000（69.9%）
    平均比值（贪心 / 最优）：0.9861
    最差的一次：73.5%

三个数分开看：

最差那次长这样（容量 22）：

      物品  1：重  7，价值  1（单位价值 0.14）
      物品  2：重  3，价值  7（单位价值 2.33）
      物品  3：重  9，价值 13（单位价值 1.44）
      物品  4：重 10，价值 14（单位价值 1.40）
      物品  5：重  2，价值  3（单位价值 1.50）
      物品  6：重  8，价值  1（单位价值 0.12）
      物品  7：重  2，价值  2（单位价值 1.00）
    贪心拿到 25，最优是 34 —— 只拿到 73.5%

两个容易读错的地方

第一：69.9% 不能和 14.1 节的 2.5% 直接比。

两个数字问的是不同的问题：

节	问的是	口径
14.1	给定一个币制，所有金额是不是都对？	同一个币制下的全部金额，一次失败就判该币制不合格
14.3	给定一个实例，这一次是不是恰好命中？	每个实例独立，互不影响

换句话说：69.9% 只说明"随机撞上一半以上的概率不低"， 不是"多数情况下可靠" —— 因为它对"最坏情况"只字未提。

第二：平均比值 0.9861 看起来很安慰，但它挡不住任何东西。

平均值的意义依赖于"最坏情况有界"。而 (B) 那个构造已经证明：最坏情况没有界。

一个系统的可用性，取决于它最差的那一次，而不是平均那一次 —— 这和 1.3 节"SLA 必须按最坏情况定"是同一条原则。

四、只改一个字：分数背包为什么就精确了

现在把"不能切分"改成"可以切分"，贪心策略一个字不改。

      容量 = 10，物品 A(重6,值30)、B(重5,值20)、C(重5,值20)
      0/1 背包的贪心：30（拿不了 B+C）
      分数背包的贪心：46.0（拿 A 的 6/6，再拿 B 的 4/5）
      而 0/1 背包的【最优】才 40

注意最后一行：分数背包的答案（46.0）比 0/1 背包的最优解（40）还高。

这不矛盾 —— 分数背包允许切分，它的约束更松，可行解集合更大，最优值自然更高。

但这个 46 和那个 40 不能拿来比较优劣 —— 它们不是同一个问题的答案。

任何时候看到"这个算法的最优值是 X，那个是 Y"，先问一句： 它们优化的是同一个可行解集合吗？ 不是的话，大小关系说明不了任何事。

在实验二那 1000 个实例上再验一遍：

    分数背包贪心值 < 0/1 背包最优值的实例数：0（应为 0）
    分数背包比 0/1 最优平均高出：3.8%

没有任何一个实例违反"分数 ≥ 0/1" ✓

为什么"允许切分"这么关键？

不能切分时，一个物品是【全有或全无】的 —— 拿了它，容量就少一整块，可能刚好让另外两个"本来能装下"的物品装不下。

能切分时，这种"整块跳变"消失了： 容量永远可以被【用满】，每一步的选择都不影响"后面还能不能继续装"。

局部最优于是真的导向全局最优 —— 这正是"贪心选择性质"。

用 14.1 的语言再说一遍：

所以"只改一个字"这个说法要精确一点：

改的不是"能不能切分"这个描述，而是【问题的数学结构】—— 从"整数规划"变成了"线性规划"，从"离散选择"变成了"连续分配"。

一字之差，是两座不同的山。

五、贪心失效的四类信号

前面三节一共出现了四种"贪心失效"的形态。把它们整理成一张可以拿来做判断的表：

怎么用这张表？

拿到一个新问题，不要先想"用什么贪心"，而是先扫一遍这四类信号。

中了一条，就要保持警惕；中了两条以上，基本可以直接放弃贪心、上动态规划。

反过来，如果一条都没中，恭喜 —— 但这仍然不是证明： 14.1 说过，验证贪心正确只有两条路（交换论证 / 小规模对拍），这张表只是帮你决定"值不值得去证"。

六、转向动态规划的判断

贪心出局之后，问题并没有解决。 接下来怎么办？

14.1 节给过一条实操心法：先想清楚"最优子结构"是否成立 —— 它成立，就意味着问题可以"由子问题的最优解拼出来"，那就有递归求解的可能。

而这正是动态规划的入口：

看这三行代码的右边：它们都是同一个形状 —— "枚举所有可能的上一步，取最好的那个"。

这正是 14.1 那句"贪心是 DP 的退化特例"的落地：

贪心每个状态只走一条路（拿最大的 / 拿单位价值最高的）； DP 走所有路（所有面额 / 所有物品），然后取最优。

而 DP 之所以敢走所有路，是因为它把"走过的状态"记下来了 —— 这正是第 15 章"记忆化"要讲的东西。

下一章会从最笨的地方开始：先写一个朴素递归，看它慢到什么程度（2.1 节的 Fib(35) 调用了 2986 万次）， 然后加一张表把它救回来。

七、练习

练习 14.3.1（手工构造反例） 自己设计一组 0/1 背包数据，满足：

(a) 容量 8，三个物品，让"按单位价值贪心"拿到的总价值不到最优的 70%。 (b) 验证你构造的例子（算出贪心值和最优值）。 (c) 你的例子里，贪心错在"拿了哪个物品"？

练习 14.3.2（判断） 判断对错并说明理由： (a) 0/1 背包的贪心最多少拿 50%。 (b) 分数背包的贪心是最优的，因为它也是"每次拿单位价值最高的"。 (c) 如果背包容量足够大（能装下所有物品），贪心一定正确。 (d) 平均比值 0.98 说明这个贪心"基本可用"。

练习 14.3.3（四类信号） 用第五节的四类信号，判断下面几个问题能不能用贪心，并说明命中了哪条信号：

(a) 一堆任务，每个有截止时间和耗时，最多能完成几个？（提示：每次选截止时间最早的） (b) 一堆硬币，每种面额无限多，凑出金额 X 且张数最少（币制是人民币） (c) 一堆物品，每个有重量，装进若干容量相同的箱子，用的箱子数最少 (d) 一群人排队接水，每个人接水时间不同，怎么排让所有人的平均等待时间最短

练习 14.3.4（工程判断） 小陈要做一个"给用户推荐优惠券组合"的功能（14.1 练习 14.1.4 的那个场景）。现在他有了本节这张表：

(a) 这个功能命中了第几类信号？ (b) 如果券的数量只有 5 张，他会怎么做？ (c) 如果有 200 张券呢？先说说会撞上什么麻烦。

八、练习答案

14.3.1

(a) 一组可行的构造

  容量 = 8
  物品 A：重 5，价值 10（单位价值 2.00）  ← 单位价值最高
  物品 B：重 4，价值 7 （单位价值 1.75）
  物品 C：重 4，价值 7 （单位价值 1.75）

(b) 验证

贪心：先拿 A（重 5，单位价值 2.00 最高），剩余容量 3 —— B 和 C 都装不下。

总价值 = 10。

最优：B + C = 重 8（刚好装满），总价值 = 7 + 7 = 14。

比值：

$$\frac{10}{14} \approx 71.4\%$$

嗯，71.4% 还差一点点没到 70%。把 A 的价值降到 9：

  容量 = 8
  物品 A：重 5，价值 9 （单位价值 1.80）  ← 仍然最高
  物品 B：重 4，价值 7 （单位价值 1.75）
  物品 C：重 4，价值 7 （单位价值 1.75）

贪心 = 9（拿 A），最优 = 14（拿 B+C），比值 = 64.3% ✓ 低于 70%

注意 A 的单位价值必须仍然最高（1.80 > 1.75），否则贪心第一步就不会拿 A，反例就不成立了。 这个"必须仍然最高"的约束，就是构造这类反例的关键。

(c) 贪心错在拿了 A。

它的判断依据是"单位价值 1.80 是全场最高"，这个判断本身没错 —— 错的是它没考虑"拿了 A 之后，剩下的 3 格容量什么都装不下"。

这就是第五节的信号 1：拿了一个，会挤掉另外几个。

14.3.2

(b) 这一条辨析很重要：如果只记"分数背包的贪心是对的"这个结论，会误以为"按单位价值排序"这个技巧本身有什么魔力。

真正起作用的是"线性"这个结构 —— 而 0/1 背包把它破坏了。

14.3.3

(a) 能用贪心 ✓

这就是"区间调度"的变体（每个任务是一个区间 $[0, 截止时间)$，选中的任务互不重叠）。

命中信号：无。

14.2 已经把交换论证走完了 —— 这是"已证过的贪心"，直接用。

(b) 能用贪心 ✓（但要小心）

人民币的币制是"规范币制"（每个面额都是更小面额的整倍数），所以"每次拿最大的"是对的。

但这条结论【依赖币制】 —— 14.1 实测：随机币制里只有 2.5% 全对。

命中的信号：信号 2（兑换率不固定）—— 只是人民币恰好没有这个问题。

所以这里要标注一个前提：如果有一天币制改了（比如发行了 7 元面额），这行代码就不再正确。

这就是 14.1 说的"贪心的错误是静默的" —— 它不会报错，只会少找几张。

(c) 不能用贪心（装箱问题，NP 难）✗

命中的信号：信号 1（打包效应）。

为什么？ "每个箱子尽量装满"这个贪心看起来很合理，但一个箱子怎么装，会影响后面的箱子还能不能装下别的 —— 和 0/1 背包是同一类耦合。

而且装箱问题比 0/1 背包更难：它是 NP 难的（不存在多项式时间的精确算法）。 实际工程里用的是近似算法（首次适应、最佳适应等），这已经超出本书范围。

(d) 能用贪心 ✓

策略：按接水时间从短到长排。

命中信号：无。

为什么对？ 直觉上很好理解：让快的人先接，后面所有人的等待时间都少算了这个"快" —— 用 14.2 的交换论证可以严格证明（把"长"和"短"的相邻两人交换，总等待时间一定下降）。

这个问题的官方名字叫"最小化平均完成时间"，它还有一个更常见的表述： "最短作业优先"（SJF） —— 操作系统调度里那个经典策略。

14.3.4

(a) 命中了信号 4（门槛 / 阶梯 / 互斥）。

"满 X 减 Y"的门槛，让"这张券能不能用"依赖于【前面的选择累积出来的订单金额】 —— 可行性本身是耦合的。

顺便一提，它其实也沾了信号 1 的边：选了一组券，可能就凑不出某个门槛了。

(b) 5 张券：暴力枚举所有子集。

$2^5 = 32$ 种组合，全部算一遍取最优 —— 毫秒级，而且绝对正确。

这就是 14.1 节说的"小规模对拍"手法的【生产化用法】： 当暴力可行时，暴力就是最优解 —— 别用贪心，也别用 DP。

(c) 200 张券：$2^{200}$ 完全不可行 —— 会撞上三件事。

这三点合起来说明：这是一个"建模"问题，不是一个"算法"问题。

正确的做法是【先把业务规则简化成数学模型】，再看这个模型有没有高效算法 —— 如果简化后是 0/1 背包，就用第 15 章的 DP；如果简化后仍然带着一堆互斥规则，那它可能是 NP 难的， 这时候要谈的是"接受近似解"还是"缩减问题规模"，而不是"用哪个算法"。

这也是本书反复出现的主题（12.4 节的排课、13.4 节的套利）： 难点往往不在算法，而在把业务问题翻译成可解的模型。

九、常见错误

十、本节总结

1. 背包问题只差一个字：分数背包（可以切分）vs 0/1 背包（全有或全无），同一个贪心策略，命运完全不同。
2. 0/1 背包的反例：容量 10，A(6,30) / B(5,20) / C(5,20) —— 贪心拿 A 得 30，最优是 B+C 得 40，只有 75.0%。
3. 差距无界（本节最重要的实测）：容量 $W$、一个"重 1 值 2"和一个"重 $W$ 值 $W$" —— 比值 $W/2$， $W=100{,}000$ 时就差 5 万倍。没有任何"最多差百分之多少"的保证。
4. 随机实例实测：1000 个实例里 699 个恰好命中（69.9%），平均比值 0.9861，最差 73.5%。
5. 69.9% 不能和 14.1 的 2.5% 直接比 —— 口径不同（"全部金额都对" vs "每个实例恰好命中"）。
6. 分数背包为什么精确："允许切分"消除了"全有或全无"的跳变，容量连续可分，选择之间不再耦合 —— 这正是"贪心选择性质"。实测 1000 个实例零违反"分数 ≥ 0/1"，平均高出 3.8%。
7. 贪心失效的四类信号：打包效应 / 兑换率不固定 / 代价可为负 / 门槛阶梯互斥。 中一条要警惕，中两条以上直接放弃贪心。
8. 转向 DP 的信号：最优子结构还在，但贪心选择性质没了 —— 那就把"一条路"扩展成"所有路"（第 15 章）。

本章小结：第 14 章把"贪心"讲完了。

• 14.1 适用条件：两个前提（最优子结构 + 贪心选择性质），贪心是 DP 的退化特例（一条路 vs 所有路）。 实测：随机币制里找零贪心只有 2.5% 全对。
• 14.2 两个成功案例：区间调度（交换论证完整演练，三种策略正确率 62.5% / 21.3% / 100%）、 Huffman 编码（最优前缀码，真实英文省 16.7%，离一元熵只差 0.048 位）。
• 14.3 失效反例：0/1 背包的近似比无界，而只改一个字（允许切分）就精确了。

贯穿本章的一条线索：

"贪心什么时候能信？" —— 14.1 给了两个前提，14.2 给了一个证明方法（交换论证）， 14.3 给了四类反例信号。答案不是"感觉对就行"，而是"能证，或者至少对拍过"。

另一条更底层的线索：

贪心的错误是【静默的】（14.1 首次提出，14.2 和 14.3 各给了一次量化）： 区间调度的"时长最短"策略 78.7% 的情况会错，找零的贪心 97.5% 的币制会错， 但两者都不会报错 —— 只会少排几个会议、少找几枚硬币。

下一章衔接：本章反复说"贪心是 DP 的退化特例"，但一直没有真正展开 DP。

第 15 章从头讲起：先写一个最笨的递归（2.1 节的 Fib(35) 调用了 2986 万次）， 然后加一张表，把它救回来 —— 这就是记忆化。

从"每个状态只走一条路"到"每个状态走所有路但只算一次"，中间隔着的就是那张表。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "14.3",
  "title": "贪心失效的反例",
  "covered": [
    "分数背包 vs 0/1 背包：只差「能不能切分」，同一个贪心命运不同",
    "0/1 背包的具体反例（容量 10，贪心 30 最优 40）与「错在第一步」的分析",
    "近似比无界的构造与实测（W 从 100 到 100,000，比值 W/2）",
    "随机实例对拍：1000 个实例 699 个恰好命中、平均比值 0.9861、最差 73.5%",
    "「69.9% 不能和 14.1 的 2.5% 直接比」的口径辨析",
    "分数背包为什么精确：「全有或全无」的跳变消失、容量连续可分",
    "实测分数背包贪心值恒 >= 0/1 背包最优值（1000 个实例零违反）",
    "贪心失效的四类信号（打包效应 / 兑换率 / 负代价 / 门槛互斥）",
    "转向 DP 的判断：最优子结构还在、贪心选择性质没了",
    "第 14 章全章小结与「静默错误」这条线索"
  ],
  "unresolved": [
    "0/1 背包的动态规划解法留到 15.3",
    "装箱问题是 NP 难，超出本书范围",
    "分数背包最优性的严格证明未展开（只给了结构解释）"
  ],
  "canonical_terms": {
    "0/1 背包（0/1 Knapsack）": "每个物品要么整个拿走、要么不拿的背包问题；贪心近似比无界",
    "分数背包（Fractional Knapsack）": "允许把物品切分开来拿的背包问题；按单位价值贪心即为最优解",
    "近似比（Approximation Ratio）": "近似解与最优解的比值；有界即可用，无界则无保证"
  },
  "symbols_units": {
    "W": "背包容量（实验一 B 中同时用作物品 B 的重量与价值）",
    "dp[c]": "容量为 c 时能装下的最大价值"
  },
  "assumptions": [
    "读者已掌握 14.1 的两个前提与 14.2 的交换论证",
    "读者理解 1.3 节「SLA 按最坏情况定」这条原则",
    "暴力枚举只用于小规模（<= 15 个物品）验证，未使用动态规划（留给第 15 章）"
  ],
  "word_count_actual": 4001,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch14/Sec143/",
    "实验一 (A)：容量 10 的小反例（贪心 30 / 最优 40 / 75.0%）为实测",
    "实验一 (B)：W=100/1,000/10,000/100,000 四档，比值 50/500/5000/50000 倍，为实测",
    "实验二：1000 个随机实例（seed=20260918）699 个恰好命中、平均比值 0.9861、最差 73.5% 及该实例的完整物品表，均为实测",
    "实验三：分数背包小例 46.0 vs 0/1 最优 40；1000 个实例零违反、平均高出 3.8%，均为实测",
    "术语写法与 glossary.md 一致（贪心算法、贪心选择性质、最优子结构）"
  ],
  "known_issues": [
    "初版实验二的说明文字写死了「平均比值 0.9 上下」，与实测的 0.9861 不符 —— 改为按实测数值描述，并把「69.9% 与 14.1 的 2.5% 口径不同」这个辨析补进正文（初版只有数字没有辨析，读者很容易误读成「背包上贪心更可靠」）",
    "代码里有一处 Console 误写成 console，编译失败 —— 已修正",
    "练习 14.3.1 初次构造（A 重5值10、B/C 重4值7）只让贪心拿到 71.4%，未达到题目要求的「不到 70%」—— 把 A 的价值降到 9（单位价值 1.80，仍高于 B/C 的 1.75）后为 64.3%，并在答案里点明「A 的单位价值必须仍然最高」这个构造约束"
  ],
  "next": "15.1 从暴力递归到记忆化"
}