前面十九章，每一章都在教你「怎么把一个算法写对」。
这一章教你怎么确认自己写错了。
主角是三个错误的贪心 —— 而且是那种**你看了会点头说「这不是显然的吗」**的错误贪心。 每一个都配一台对拍器：不用你动脑，点一下开始，几秒钟之内它就会当着你的面崩掉。
为什么值得花一整章干这件事？因为贪心是唯一一类 **「代码没写错、样例全过、编译零警告，但整个想法是错的」**的算法。 这种错误在考场上不会有任何提示 —— 除非你自己先动手打假它。
1 案例一：找零钱
m 种面额的硬币（每种无限多，且含面额 1），要凑出金额 x，最少要几枚？
几乎所有人的第一反应都是：从大到小，能拿就拿。 而且这个直觉有极强的现实依据 —— 你每天用的人民币面额 1 2 5 10 20 50 100，这么找零一定是最省的。
点「运行 ▶」看结果
面额 {1, 3, 4}，要凑 6：
| 方案 | 枚数 | |
|---|---|---|
| 贪心 | 4 + 1 + 1 | 3 枚 |
| 最优 | 3 + 3 | 2 枚 |
一个小到可以口算的例子，贪心就输了。
注意贪心并没有「走错某一步」：它拿 4 的时候，4 确实是当时能拿的最大面额。 错的是「每步拿最大」这个想法本身。
2 标准答案要用完全不同的思路写
要打假它，先得有个绝对可靠的东西。这里用 DP（就是第 24 章的完全背包，提前见个面）：
点「运行 ▶」看结果
dp[i] = min(dp[i - c] + 1)：它枚举了最后一枚硬币是哪种面额，一种都没漏。
而贪心是直接断定「应该拿最大的」。
DP 全试，贪心直接选 —— 这就是两者的全部区别，也是为什么 DP 不需要证明而贪心需要。
对拍的铁律（第 9、15 章都强调过）：两份程序的思路必须不同。 同一个想法写两遍，只能验出打字错误；这一章要抓的恰恰是想法错误。
3 ★ 对拍：让它当着你的面崩掉
前面几章，「正解」那一栏放的是正确的代码，让你换成自己写的。
这一章不一样：那一栏里预置的就是错误的贪心。 直接点「开始」， 看它撑不撑得过三轮。然后你再把它换成你以为对的版本，再跑一次。
本机用种子 1~300 跑出来的结果：
| 错误的贪心 | 300 轮里错了几轮 | 第几轮第一次被抓 |
|---|---|---|
| 找零钱：从大到小拿 | 34 轮 | 第 4 轮 |
| 01 背包：按性价比拿（第 6 步） | 151 轮 | 第 3 轮 |
| 区间调度：按左端点排（第 10 步） | 37 轮 | 第 2 轮 |
找零钱那个贪心，300 轮里有 266 轮是对的 —— 将近九成。
这正是它可怕的地方：
- 你手算几个例子 → 全对；
- 你过了样例 → 全对；
- 你随便试三五组数据 → 大概率全对；
- 你交上去 → WA 三个点。
「试了几组都对」不是证据，一次都不是。 只有两种东西算证据： 一个能走通的证明（第 19 章的交换论证），或者一台跑了几百上千轮的对拍器。
4 动画：贪心到底在第几枚上走岔
上排是贪心一枚一枚拿的过程，下排是 DP 算出来的最优方案。 红色那一枚就是两边第一次不一样的地方 —— 贪心从那里开始走岔，后面全是徒劳。
建议这样玩：
- 默认
{1,3,4}凑 6，看它在第一枚上就岔了； - 把面额改成
1 2 5 10（人民币），把x改成任意数 —— 怎么试都岔不了； - 再改成
1 5 8，点「跳到最小反例」，看它跳到 10（8+1+1输给5+5）。
5 ★ 对拍没抓到，能说明贪心是对的吗
一般情况下：不能。
对拍是证伪工具，不是证明工具。它跑 1000 轮没出事，只说明
「在你造得出来的这类数据上没出事」。反例可能恰好在你的生成器造不出的形状里 ——
比如你的 n 只到 10，而反例最小需要 11 个物品。
能证明贪心正确的只有证明本身（第 19 章的交换论证）。 对拍的作用是：在你花两小时证明之前，先花三分钟确认它值不值得证。
不过找零钱这道题有个漂亮的例外，值得单独讲：
点「运行 ▶」看结果
对一套面额 1 = c₁ < c₂ < … < cₘ：
如果它存在反例，那么最小的那个反例一定小于「最大的两个面额之和」cₘ₋₁ + cₘ。
于是只要在这个范围里扫一遍没找到反例，就可以断言：这套面额下贪心永远正确 ——
对所有的 x，无穷多个。
这就是「证明」和「对拍」的区别： 对拍说「我试过的都没事」，定理说「不用试了，永远没事」。
coinFind.cpp 会把这件事一起验给你看：它先在上界内找最小反例，
再故意往外多扫 500 —— 你会发现外面确实不会冒出更小的意外。
（npm run check:viz 也在替你反复验这条定理，六套面额，每次跑都验一遍。）
6 案例二：01 背包按性价比 —— 最著名的那个上当
n 件物品，第 i 件价值 v[i]、重量 w[i]，每件只有一个、不能切开。
背包能装 W 的重量，求最大总价值。
「先拿性价比（价值÷重量）最高的」—— 这个直觉比找零钱那个还要强烈， 因为它在部分背包里是有严格证明的（第 9 步会讲）。
点「运行 ▶」看结果
W = 50：
| 物品 | 价值 | 重量 | 性价比 |
|---|---|---|---|
| A | 60 | 10 | 6.0 |
| B | 100 | 20 | 5.0 |
| C | 120 | 30 | 4.0 |
- 贪心：拿 A（占 10）、拿 B（占 20），剩下 20 装不下 C → 160
- 最优：B + C = 220
差了 60。而贪心每一步都拿了当时性价比最高、又装得下的那件 —— 一步都没走错。
7 换个排法行不行？三种一起试
很多人的下一反应是「那我换个关键字排」。这份代码一次性回答：
点「运行 ▶」看结果
上面那组数据跑出来：
| 策略 | 总价值 |
|---|---|
| ① 先拿价值最大的 | 220 |
| ② 先拿重量最小的 | 160 |
| ③ 先拿性价比最高的 | 160 |
| ④ 枚举全部子集（一定最优） | 220 |
| ⑤ 同一个③，但允许切开 | 240.00 |
「先拿价值最大的」在这组数据上给出了 220，正好等于最优。
这恰恰是本章第 3 步那个结论的又一次演示：错误的贪心经常蒙对。 把这组数据丢进下面的对拍器，换成 ① 试试，它照样会在几轮内崩掉。
8 动画：一步都没走错，结果还是错的
物品已经按性价比从高到低排好。左边是贪心的决定，右边是最优解的决定， 红色那一行就是两边第一次做出不同决定的物品。
右下角三个数字并排放着，是这一章的题眼：160（01 背包贪心）、220（01 背包最优）、240（可切开时的贪心）。
9 ★ 关键一步：同一个贪心，为什么在部分背包里就对了
点「运行 ▶」看结果
部分背包的证明：
设最优解里装了一部分低性价比的货 y，同时还有高性价比的货 x 没装满。
把 y 拿出来一点点（重量 δ），换进同样重量的 x：
总重量没变，价值变化 = δ · (x的性价比 − y的性价比) > 0严格变好。所以最优解里不可能出现这种情况 —— 最优解一定是「性价比从高到低装，最后一件切开」，也就是贪心。∎
现在把这段论证搬到 01 背包： 「拿出来一点点、换进去一点点」这一步做不了 —— 物品不能切。 你只能整件换，而整件换会留下一个填不满的空隙，空隙是白白浪费的。
论证在哪一步断掉，反例就长在哪里：教科书那个反例里， 贪心拿完 A、B 之后剩下的那 20 的空隙，就是它输掉的 60。
贪心的正确性属于问题，不属于算法。
「按性价比排序的贪心对不对」这个问句本身就是错的 —— 必须问 「按性价比排序的贪心，在这个问题上对不对」。
同一份代码，物品能切就对，不能切就错。
所以永远不要凭「我以前做过一道类似的题，那题就是这么贪的」来判断。 类似的题，条件差一个字，答案就换一边。
10 案例三：回到第 19 章那道区间调度
第 19 章已经证明过「按右端点排」是对的。这里把错误版拿出来，让你亲手打假它：
点「运行 ▶」看结果
11 ★ 能打假贪心的生成器，是怎么设计出来的
【1】随机的必须是「贪心依赖的那个东西」，不是规模。
- 找零钱：贪心依赖面额，所以要随机面额 —— 随机金额没用。
- 01 背包：贪心依赖性价比的排序，所以要让重量和容量同一量级，让空隙致命。
- 区间调度：贪心依赖端点的相对位置，所以坐标范围要小，让区间大量重叠。
【2】范围要小，不是大。
反例几乎总是小的。n = 3、坐标 1~14、面额 ≤ 25 —— 这一章三个反例分别只有
3 件物品、3 场比赛、3 种面额。把 n 开到 1000 只会让暴力跑不完，
而跑不完的对拍等于没有对拍。
【3】故意混入「贪心是对的」那类数据。
coinGen.cpp 里有三分之一的数据是人民币面额 —— 贪心在那上面永远正确。
留着它是有意的：让你亲眼看见**「有时候对」和「总是对」完全是两回事**。
12 ⚠ 对拍的三个盲区（必须知道）
如果标准答案和「正解」是同一个人、用同一个思路写的，那么想错了的地方会一起错， 对拍全绿，但两份都是错的。
破法：标准答案一定要用完全不同的思路（这一章用 DP 和 2ⁿ 枚举，都不是贪心）。
对拍用的是 n ≤ 12 的小数据，int 和 long long 在那里的表现完全一样。
第 19 章那个「总等待时间要用 long long」的坑，对拍永远不会告诉你。
破法：只能靠脑子。凡是「一堆数加起来 / 乘起来」的答案，先写 long long。
这一章的部分背包答案是小数。两份程序的计算顺序稍有不同，
末位就可能差一点点，直接 == 会报出一堆假的「不一致」。
而且这个坑比想象的深：C++ 的 setprecision(2) 用的是四舍六入五成双，
77.625 输出成 77.62；而 JavaScript 的 toFixed(2) 是逢五就进，输出 77.63。
同一个数，两种语言的「保留两位」结果不一样。
（这不是编的 —— 这一章的动画交叉验证就是被这个绊住的，脚本里现在写着一行注释记着它。）
破法：比较浮点要用「差值不超过某个容差」，比如
fabs(a - b) <= 1e-6，或者按输出精度的一半来卡。
更省事的办法是让题目里的答案变成整数（比如输出「答案 × 100 的整数部分」）。
13 ★ 拿到一道疑似贪心的题，按这个清单走
-
先写暴力。 2ⁿ、n!、DP，怎么慢怎么来 —— 它是你唯一的尺子。 没有尺子，后面每一步都是猜。
-
猜一个贪心策略，试着做交换论证。 假设最优解和贪心在某处不同 → 把它换成贪心的选择 → 证明不会变差。
- 论证走通了 → 你知道它对，而且知道为什么；
- 论证卡住了 → 卡住的那一步就是反例的形状。 （部分背包 → 01 背包，卡在「不能切开」，反例就是「填不满的空隙」。）
-
不管论证通没通，都去对拍。 300 轮起步，生成器按第 11 步那三条设计。
-
对拍绿了，也要回头看第 12 步那三个盲区。
-
实在证不出来又不敢赌，就上 DP。（阶段 5 马上就到。） 慢一点的正确算法，永远好过快一点的错误算法 —— 考场上前者拿 70 分，后者拿 0 分。
第 19 章教的是怎么把贪心写对：排序型贪心的形状，以及交换论证怎么做。
第 20 章教的是怎么确认自己没写错：错误的贪心长什么样、 生成器怎么设计才打得中要害、以及对拍治不了的三种病。
合起来是一句话： 贪心不是「感觉对就写」，是「说得出为什么对、并且用机器验过」才写。 说不出、也验不动的时候，老老实实上 DP —— 下一阶段就是它。
14 自测
- 洛谷 P1080 国王游戏 —— NOIP2012。交换论证的教科书题：按 a×b 排序。先自己推交换论证，再看题解。（要写高精度，可以先只做证明部分）
- 洛谷 P1048 采药 —— NOIP2005。就是本章的 01 背包 —— 故意先用性价比贪心交一发，看着它 WA，再学第 23 章的 DP。这一发 WA 值得挨
- 洛谷 P2240 部分背包问题 —— 同一个贪心，这里是对的。和上一题对照着做，本章第 9 步那段论证会刻进脑子里
- 洛谷 P5019 铺设道路 —— NOIP2018。贪心是对的，但你得说得出为什么。先写暴力对拍，再想证明
- 洛谷 P1090 合并果子 —— NOIP2004。「每次合并最小的两堆」是对的，但「一次排序后顺着合并」是错的 —— 又一个「差一点点就错」的例子。第 37 章会用堆重做它
阶段 5 · 动态规划，从第 21 章开始。
开场白就是这一章的结尾：当你证不出贪心、又不敢赌的时候，DP 是那个「一定对」的退路。 它的代价是慢一点、代码长一点，换来的是「所有可能都试过了」的踏实。
而且你已经见过它了 —— 第 17 章的记忆化搜索、本章的 coinDp.cpp，
都是 DP。第 21 章要做的只是把它讲明白。