N 皇后里那句 if (col[c] || d1[...] || d2[...]) continue; 就是最基础的剪枝。
这一章把剪枝系统化成三板斧，并且用一张实测表告诉你每一招值多少钱 —— 其中有一条结论相当反直觉，第 6 步会看到。
搜索题在竞赛里的地位很特殊：不会做的题，写个搜索至少能骗到部分分； 而会不会剪枝，决定你骗到 30 分还是 100 分。
1 一句话问题
n 只猫要坐缆车下山，第 i 只重 w[i]。每辆缆车载重上限 W，
一辆车可以载任意多只猫，只要总重不超过 W。最少要几辆车？
输入 5 100
60 40 50 30 20
输出 2
[60 40] 和 [50 30 20]，两辆车正好「从大到小，能塞就塞」听起来很合理，但它会错。
反例：W = 10，猫重 6 5 5 4。
贪心：6 装一车（放不下 5），5+5 一车，4 一车 → 3 辆。
最优：6+4 和 5+5 → 2 辆。
这是经典的装箱问题，已知没有多项式时间的精确算法 —— 所以只能搜索。而搜索能不能过，就全看剪枝了。
2 搜索的形状
一只一只地安排猫。第 i 只猫有两类选择：
- 塞进某一辆已经开出去的车（如果装得下）
- 新开一辆车
全部安排完，用了几辆车就是一个候选答案。这就是第 4 章那个框架：
void dfs(int i) {
if (i == n) { best = min(best, carCount); return; }
for (int j = 0; j < carCount; j++) // 选择一：塞进已有的车
if (load[j] + w[i] <= W) {
load[j] += w[i]; dfs(i + 1); load[j] -= w[i]; // 进入→递归→撤销
}
load[carCount++] = w[i]; // 选择二：新开一辆
dfs(i + 1);
load[--carCount] = 0;
}点「运行 ▶」看结果
3 实测：不剪枝有多惨
本机实测：
| n | 不加剪枝 | 剪枝全开 |
|---|---|---|
| 17 | 0.75 秒 | 0.003 秒 |
| 18 | 3.42 秒 | 0.003 秒 |
| 19 | 14.9 秒 | 0.003 秒 |
| 20 | 77.9 秒 | 0.004 秒 |
n 每加 1，不剪枝的版本就慢四五倍；而剪枝版本几乎没有反应。
4 ★ 剪枝三板斧
【1】可行性剪枝 —— 「这条路走下去一定违规」
if (load[j] + w[i] <= W) // 装不下就根本不进这个分支最基本的一类，brute.cpp 里就有。凡是「走下去必然不合法」的分支，立刻掐掉。
【2】最优性剪枝 —— 「这条路走下去一定不如已有答案」
if (carCount >= best) return; // 已经追平最优了，再搜也不可能更好注意它有个前提：必须先有一个答案。所以要让搜索尽快摸到一个像样的解 —— 这就引出第三板斧。
【3】搜索顺序 —— 「先走最容易失败 / 最容易出好结果的分支」
sort(w.begin(), w.end(), greater<long long>()); // 先安排重的猫重的猫选择少、最容易失败，也最容易把车「填实」。把它们放在前面，
搜索的第一条路径通常就相当不错，best 立刻变小。
5 正解
点「运行 ▶」看结果
搜索的形状一点没变，只多了一句 if (carCount >= best) return; 和一行排序。
点「运行 ▶」看结果
6 ★ 每一招到底值多少钱（这里有个反直觉的结论）
点「运行 ▶」看结果
本机实测（n = 17，W = 100）：
| 组合 | 答案 | 搜索节点数 | 耗时 |
|---|---|---|---|
| ① 什么都不加 | 7 | 203 232 788 | 1084 毫秒 |
| ② 只加最优性剪枝 | 7 | 64 226 | 0.40 毫秒 |
| ③ 只把猫从重到轻排序 | 7 | 172 139 308 | 552 毫秒 |
| ④ 两个都加 | 7 | 1 799 | 0.01 毫秒 |
先看 ③：只排序、不加最优性剪枝，几乎没用（2.03 亿 → 1.72 亿）。
为什么？因为排序本身不剪掉任何分支，它只是换了个走的顺序。 整棵搜索树该多大还是多大。
再看 ④：排序 + 最优性剪枝 = 1 799 个节点，比只加最优性剪枝的 ② 又快了三十多倍。
原因：先安排重的猫，搜索的第一条路径就已经接近最优，best 立刻降到很小的值；
而 best 越小，if (carCount >= best) return; 这一刀砍得越狠。
结论：搜索顺序单独用没意义，它是用来让别的剪枝提前生效的。 这是很多人学剪枝时想不通的一点 —— 记住它，会省你很多调试时间。
四种组合的答案完全一样，都是 7。
剪枝不会改变答案，它只砍掉「不可能更优」和「必然违规」的分支。 如果你加了个剪枝之后答案变了，那不是剪枝生效了，是你剪错了 —— 剪掉了本来可能是最优解的分支。
这也是为什么这一章的对拍如此重要：它专门用来抓「剪过头」。
7 单步玩剪枝开关
| ① 什么都不加 | 158 |
| ② 只加最优性剪枝 | 24 |
| ③ 只从重到轻排序 | 156 |
| ④ 两个都加 | 21 |
上面那两个按钮就是开关。同一组数据，四种组合的节点数实时列在右边。
建议这样玩一遍：
- 两个都关 → 记下节点数
- 只开「从重到轻」→ 几乎没变（就是上一步说的那个反直觉结论）
- 只开「最优性剪枝」→ 断崖式下跌
- 两个都开 → 再降一个数量级
然后把猫的重量改成全都很接近 W（比如 90 85 95 88 92），
看看节点数变化 —— 那时几乎一猫一车，搜索树反而很浅。
8 ★ 对拍：专门抓「剪过头」
把「剪枝全开」那一栏换成你自己写的（包括你自己想出来的额外剪枝），再点开始。
这个对拍的意义和前面几章不太一样：它不是在验证「你写得快不快」， 而是在验证「你有没有剪掉本来该要的答案」。
剪枝写错了不会报错、不会超时，只会安安静静地给出一个偏大的答案。 不对拍根本发现不了。
值得故意写错的，每一个都是「剪过头」的典型：
if (carCount >= best) return;写成>→ 剪得不够，慢但答案对（这个反而无害）if (carCount > best) return;改成if (carCount + 1 >= best) return;→ 剪过头了，答案偏大 —— 对拍立刻抓住- 加一个「看起来对」的剪枝：如果剩下的猫总重 > 剩余车的空余容量就返回 → 想清楚「剩余车」指什么，很容易写错
- 排序写成从轻到重 → 答案对，但慢得多（对拍抓不住，只有 count.cpp 能看出来）
9 剪枝的通用思考方式
-
这条分支会不会违规？（可行性剪枝） —— 最容易想到，通常写代码时自然就带上了。
-
这条分支还有可能比现有答案更好吗？（最优性剪枝） —— 需要一个「当前最优」和一个「乐观估计」。 比如「现在已经用了 5 辆车，而最优是 5 辆」→ 不可能更好。 更强的版本会算「就算后面全都完美，最少还要几辆」—— 这叫估价函数，是 A* 和 IDA* 的核心。
-
先搜哪个分支，能让上面两条更早生效？（搜索顺序） —— 通常是「选择最少的」「限制最紧的」优先。
-
有没有重复的状态？（记忆化 / 判重） —— 如果两条不同的路径到达了完全相同的局面，就没必要搜两遍。 这就是第 17 章记忆化搜索。
剪枝改变的是搜索树的大小，不是每一步的速度。
所以不要指望「把 vector 换成数组」「少写一次函数调用」能救回一个不剪枝的搜索 ——
那是在 2 亿个节点上省常数，而剪枝直接把它变成不到 2 千个。
先想清楚剪什么，再考虑常数。 顺序反了就是白费力气。
10 自测
本章的原题是「小猫爬山」（AcWing 165 / 《算法竞赛进阶指南》）， 洛谷上没有完全对应的题号，所以下面换了几道同类的剪枝题。
- 洛谷 P1074 靶形数独 —— NOIP2009。搜索顺序剪枝的教科书 —— 先填候选最少的格子，和本章「先安排重的猫」是同一个道理
- 洛谷 P1120 小木棍 —— 剪枝的经典硬骨头，要用到五六种剪枝。做不出来很正常，把题解里每个剪枝都想明白就是收获
- 洛谷 P1731 生日蛋糕 —— NOI1999。最优性剪枝的教科书，需要预处理「最小体积/面积」当估价函数
- 洛谷 P1518 两只塔姆沃斯牛 —— 换换脑子：状态是「两头牛的位置和朝向」，用第 15 章的状态图思路
第 17 章记忆化搜索，正好回答上面第 4 问：如果两条路径走到了同一个状态呢？
那一章你已经学过了（它是阶段 3 的枢纽）。如果当时是跳着看的， 现在带着「剪枝」的眼光回去重读一遍 —— 你会发现记忆化其实就是第四种剪枝：把「算过的状态」整个剪掉。