第 24 章结尾你手里握着这么一张表：
| 转移右边的第一维 | 一维怎么写 | |
|---|---|---|
| 01 背包 | i-1 | 倒序 |
| 完全背包 | i | 正序 |
这一章的两道题，都不需要在这张表上加任何东西：
- 二维费用背包（同时限制重量和体积）—— 表原样就能用，只是多一层循环。 前半章真正的收获是一个你多半没想过的问题： 「两层容量循环都要倒序」这句口诀里，有一层其实是白记的。
- 分组背包（每组至多选一件）—— 也没有新公式，但三层循环的顺序不能错。 而写错的两种方式，跑出来正好分别是第 23 章和第 24 章的正确答案。
所以这一章的主题只有一句：顺序决定你读到的是上一轮还是这一轮， 而那决定了你解的是哪一道题。
1 上半场一句话问题：拿一件要同时付两种代价
物品还是「拿或不拿」，还是每件最多一件 —— 和第 23 章一模一样。
唯一的变化是：拿一件要同时付出重量 w 和体积 u，而背包对两者各有一个上限 W 和 V。
n件物品，第i件价值v[i]、重w[i]、占u[i]。 总重不超过W、总体积不超过V，求最大总价值。
不在思路上，只在下标上：
f[j] → f[j][u] 状态多一维
f[j - w] → f[j - w][u - vol] 转移的下标多一维
一层容量循环 → 两层容量循环「每件最多拿一件」这条没有变，所以转移右边的第一维还是 i-1，倒序还是倒序。
是「每件能拿几件」决定方向，不是「有几维费用」。
2 先用手算一遍：三个数字，一眼看出体积那一维在干什么
重量上限 W = 10，体积上限 V = 8
① 价值 6，重 4，占 2
② 价值 5，重 3，占 4
③ 价值 4，重 2，占 3
④ 价值 3，重 2，占 2- 只看重量（假装没有体积这一回事）：选 ①②③ → 重 4+3+2 = 9 ≤ 10，价值 15。 但它们的体积是 2+4+3 = 9 > 8 —— 装不进去。
- 两个限制都算：选 ①②④ → 重 9 ≤ 10、体积 8 ≤ 8，价值 14。这才是答案。
- 顺带看一眼完全背包（假设每件能拿无限件）：①×2 + ③ → 重 10、体积 7，价值 16。
15 → 14 → 16 这三个数后面每一步都会回来验： 15 是「忘了体积维」的答案，14 是正解，16 是「循环方向写反」的答案。
3 暴力：第 23 章那份 2ⁿ 枚举子集，改一行就能用
点「运行 ▶」看结果
改的就是那一行判断：if (sw <= W) → if (sw <= W && su <= V)。
题目多一个限制，暴力就多一个 && —— 这句话待会儿在 DP 里会变成「多一层循环」。
它慢得离谱（2ⁿ），但绝不会错，这半章的标准答案就是它。
4 ★ 关键一步（一）：多一维费用，就多一层循环
第 23 章的一维写法：
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--)
f[j] = max(f[j], f[j - w[i]] + v[i]);二维费用只要在中间塞一层：
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--)
for (int u = V; u >= vol[i]; u--) // ← 新加的一层
f[j][u] = max(f[j][u], f[j - w[i]][u - vol[i]] + v[i]);其余一个字都不用改。 为什么可以这么放心？因为第 24 章那句话：
转移右边的第一维是 i-1 还是 i，由「每件能拿几件」决定 ——
而这道题每件还是最多一件，所以还是 i-1，所以还是倒序。
时间从 O(nW) 变成 O(nWV)，空间从 O(W) 变成 O(WV)。
多一维费用的代价全在这里，第 7 步会实测。
点「运行 ▶」看结果
跑出来 14，和第 2 步手算的一样。
5 ★ 关键一步（二）：那句口诀里，有一层是白记的
几乎所有资料都会告诉你「二维费用的两层容量循环都要倒序」。这句话没错，但它多记了一半。
读 f[j-w][u-vol] 时，读到的必须是「还没放这件物品」的值。
现在盯住 f 这张表的形状：它是按外层下标 j 分成一整行一整行的。
- 外层倒序时，
j-w那一整行这一轮根本还没被碰过 —— 里面每一格都还是上一轮的值。 既然整行都没动过，那内层在这一行里从左往右还是从右往左读，读到的是同一个东西。 - 外层一旦正序，
j-w那一整行早就填完了 —— 内层再怎么倒序也救不回来。
★ 所以：方向的决定权只在外层。内层怎么写，一点关系都没有。
不用信我，跑一遍。下面这份代码是故意把内层写成正序的：
点「运行 ▶」看结果
还是 14。而且不是这一组数据碰巧 —— check:viz 拿 300 组随机数据跑过，
它和 vol2.cpp 一组不差（第 8 步那张表里，它的「被抓轮数」是 0 / 300）。
反过来，把外层写成正序：
点「运行 ▶」看结果
跑出来 16 —— 正是第 2 步手算的完全背包答案。
vol2Up.cpp 不是随机地错，它精确地解了二维费用的完全背包：
check:viz 用 300 组数据钉死了这条恒等式：两份代码的输出一组不差。
把四种写法摆在一起，这半章就说完了：
点「运行 ▶」看结果
不给输入就用第 2 步那组数据，输出：
外层容量循环 内层容量循环 答案 和两层都倒序一样 和两层都正序一样
------------ ------------ ------ ---------------- ----------------
倒序 倒序 14 是 否
倒序 正序 14 是 否
正序 倒序 16 否 是
正序 正序 16 否 是答案按外层方向分成整整齐齐的两组，内层那一列从头到尾没起过作用。
6 动画：一帧填一整行，看那一行「这轮动过没有」
这个动画一帧填一整行 f[j][*]，因为要讲的正是「整行」。
来源行只有两种颜色：绿色 = 这一轮还没碰过（还是上一轮的值），
红色 = 这一轮已经填完了。
- 外层倒序：来源行从头到尾都是绿的，「同一件最多装进同一格几次」恒为 1；
- 外层正序：红色开始出现，那个计数器涨到 2 —— 它已经不是 01 背包了。
切了之后你会发现：颜色没变、计数器没变、答案没变、连播放的步数都没变。
这不是动画坏了 —— 这就是第 5 步那个结论的画面版。 一行要么整体动过、要么整体没动过，内层在行内的先后根本影响不到这件事。
顺带一个细节值得看：外层正序时，并不是每一行的来源都是红的。
j < 2w 的那几行，来源行 j-w 这一轮还没轮到，所以是绿的 ——
红色是从 j ≥ 2w 开始出现的，而那正好就是「同一件放得下第二件」的地方。
7 实测：多一维费用要多花多少
先看 DP 相对暴力值多少（W、V 固定 200，只改物品件数 n）：
本机实测（./vol2GenBig n 200 200，固定种子）：
| n | 2ⁿ 暴力 | 三层循环 |
|---|---|---|
| 20 | 0.053 秒 | 0.005 秒 |
| 22 | 0.205 秒 | 0.004 秒 |
| 24 | 0.848 秒 | 0.006 秒 |
| 26 | 3.483 秒 | 0.005 秒 |
n 每加 2，暴力翻四倍；DP 那一列压根没动 —— 因为它的规模是 n × W × V，和 n 只是线性关系。
一维背包的 f 只有一行，W = 100000 也才 800 KB。
二维费用的 f 是一整张表，W 和 V 是乘起来的。
本机实测（./vol2GenBig 100 2000 V，固定种子，只改体积上限 V）：
| V | 耗时 | 峰值内存 | 其中这张表占 |
|---|---|---|---|
| 100 | 0.01 秒 | 5.5 MB | 1.6 MB |
| 200 | 0.02 秒 | 6.8 MB | 3.2 MB |
| 400 | 0.05 秒 | 9.9 MB | 6.4 MB |
| 800 | 0.17 秒 | 16.1 MB | 12.8 MB |
最后一列是 (W+1) × (V+1) × 8 字节算出来的，减一减就能看出剩下那 3 ~ 4 MB 是进程底噪。
W = V = 5000 时这张表就是 200 MB —— 大多数题目的空间限制是 256 MB，
所以二维费用题的两个上限通常都开得很小（P1855 是 200×200）。看到题面里两个上限都很小，
心里就该有数了：出题人是在提示你上二维费用。
（这四行的答案分别是 8546 / 8122 / 7678 / 7286。看着像「V 越大答案越小」，其实只是随机波动 ——
换个种子跑 ./vol2GenBig 100 2000 V 7，四个答案是 7711 / 8412 / 8265 / 8779，反过来了。
因为生成器把物品体积也按 V 等比例放大了：题目的难度没变，变的只有那张表的大小。）
8 ★ 对拍（一）：以及一次「生成器不狠等于白跑」的现场演示
300 轮实测，三份「改了方向或漏了东西」的代码：
| 改动 | 被抓 | 第几轮 | 它其实解了哪道题 |
|---|---|---|---|
| 外层容量循环写成正序 | 237 / 300 | 第 2 轮 | 二维费用的完全背包 |
| 把体积那一维整个忘了 | 141 / 300 | 第 2 轮 | 普通一维 01 背包 |
| 外层倒序、内层正序 | 0 / 300 | — | ← 它就是正解（第 5 步那个 ★） |
最后一行是这张表最值钱的地方：对拍抓不住它，不是因为数据不够狠，而是因为它根本没错。
我另写了一份生成器 vol2GenLoose.cpp，只改一件事：把体积上限放到大得永远吃不紧
（所有物品的体积加起来都装得下）。同样跑 300 轮：
| 改动 | 正常数据 | 体积永远吃不紧的数据 |
|---|---|---|
| 把体积那一维整个忘了 | 141 / 300 | 0 / 300 |
| 外层容量循环写成正序 | 237 / 300 | 277 / 300 |
道理简单得可怕：体积上限永远卡不住答案时，这道题本来就等于一维 01 背包 —— 体积维写没写，答案根本没区别。
这是第 7、20、22、24 章那条规矩的第五次现形： 要随机的是「算法依赖的那个量」。 这半章依赖的是「第二维吃不吃紧」， 不是 n、不是 W。一个体积永远宽松的生成器，跑一万轮也是绿的，交上去就是 WA。
9 下半场：分组背包 —— 每组至多选一件
物品被分成若干组，每组至多选一件（也可以一件都不选）。背包容量
W，求最大总价值。
这个限制比看起来常见得多：「三种显卡只能装一张」「同一门课的多个上课时段只能选一个」—— 只要出现「互斥的几个选项」，就是分组背包。
手算一组（后面每一步都会回来验）：
容量 W = 11
第 1 组： (价值 6, 重 4) (价值 5, 重 3)
第 2 组： (价值 7, 重 3) (价值 6, 重 3)
第 3 组： (价值 3, 重 2) (价值 8, 重 6)
第 4 组： (价值 1, 重 7) (价值 1, 重 8)- 正确答案：第 1 组拿
6/4、第 2 组拿7/3、第 3 组拿3/2，第 4 组整组跳过 —— 重 9 ≤ 11，价值 16。 - 要是忘了「每组只能一件」：第 2 组的
7/3和6/3一起拿，再加第 1 组的5/3和第 3 组的3/2， 重 11、价值 21。 - 要是每件还能拿无限次：
7/3拿三件 +3/2一件 = 重 11、价值 24。
16 / 21 / 24。 记住这三个数 —— 待会儿它们会分别对应三种循环顺序。
10 暴力：DFS 枚举「每组选谁」
点「运行 ▶」看结果
输入格式是本章自己定的：第一行 组数 容量，接下来每行一组
（先是这一组的件数，再跟着若干对「价值 重量」）。这样分组关系一眼可见。
洛谷 P1757 是「每件物品自带组号」，读入时归一下类就变成这个样子。
它跑出来 16，和手算一致。复杂度是 ∏(每组件数 + 1) —— 每多一组就乘一次，
第 13 步会看到它是怎么爆炸的。
11 ★ 关键一步（三）：三层循环，顺序决定你解的是哪道题
for (int gi = 0; gi < g; gi++) // ① 组
for (int j = W; j >= 0; j--) // ② 容量，倒序
for (auto& it : grp[gi]) // ③ 组内枚举 —— 必须在最里层
if (it.w <= j) f[j] = max(f[j], f[j - it.w] + it.v);★ 为什么必须是这个顺序 —— 还是那一句话，和第 23、24 章一字不差：
看你读到的 f[j-w] 是「上一轮」的还是「这一轮」的。
只不过这里的「一轮」不再是一件物品，而是一整组：
j 倒序时，f[j-w] 还没被这一组碰过 —— 它代表「前 gi-1 组的最优解」。
在它上面加一件，这一组就正好只出了一件。「每组至多一件」是这么保证的。
组内那层循环放在最里面，起的正是这个作用：本组的每一件都从同一个「本组还没出手」的 局面出发去试，试完取最好的那一个。
点「运行 ▶」看结果
现在把中间那两层换个位置：
点「运行 ▶」看结果
跑出来 21 —— 正是第 9 步那个「忘了每组只能一件」的答案。
因为这样一来，同一组的第二件读 f[j-w] 时，读到的是「第一件已经放进去」的值。
再把容量循环写成正序：
点「运行 ▶」看结果
跑出来 24 —— 正是「每件还能拿无限次」的那个答案。
同样三层循环、同样一批物品，顺序决定你解的是哪一道题：
| 怎么写 | 答案 | 它解的是 | 出处 |
|---|---|---|---|
| 组 → 容量倒序 → 组内 | 16 | 分组背包 | 本章 |
| 组 → 组内 → 容量倒序 | 21 | 无视分组的 01 背包 | 第 23 章 |
| 组 → 容量正序 → 组内 | 24 | 无视分组的完全背包 | 第 24 章 |
后两行不是「大概差不多」，是恒等：check:viz 拿 300 组随机数据，
把 groupFlat.cpp 和 groupIgnore.cpp（老老实实的 01 背包）、
groupUp.cpp 和 groupFull.cpp（老老实实的完全背包）各对了一遍，一组不差。
连着第 23 章（01 写成正序 ≡ 完全背包）、第 24 章（完全写成倒序 ≡ 01 背包）， 再加上本章前半段那条（二维费用外层正序 ≡ 二维费用的完全背包）， 背包这三章一共钉死了五条这样的恒等式。它们都在说同一件事：
DP 的循环顺序不是「格式」，它就是题目本身。 写反了不会报错、不会崩溃、不会有警告 —— 它只是安静地去解另一道题，然后把答案交给你。
12 动画：盯住格子下面那排圆点
下拉框有四档（一个正确、三个错误），但你只要盯每一格下面那排圆点 —— 那是「这一格里装了本组的几件」。题目要求每组至多一件，所以：
| 写法 | 圆点最多几个 | 答案 |
|---|---|---|
| 正确 | 1 | 16 |
| 组内枚举提到容量外 | 2 | 21 |
| 容量循环写成正序 | 3 | 24 |
| 漏掉「本组不选」这个选项 | 1 | 4 |
最后那一档（groupMust.cpp）犯的不是顺序错误，是读题错误：
把「每组至多选一件」写成了「每组必须选一件」。
代码上只少写了一点点 —— f[j] 自己没有被放进候选里：
正确： f[j] = max(f[j], f[j - w] + v); // f[j] 自己在里面 = 允许这一组不选
错误： best = 组内所有件里最好的那个; f[j] = best; // 把 f[j] 挤掉了少的那个「f[j] 自己」，就是「这一组一件都不选」这个选项。 第 4 组（又重又不值钱）本该被整组跳过，现在只能硬着头皮拿一件，答案从 16 掉到 4。
而它的圆点始终是 1 个 —— 计数器全程正常。 顺序类的 bug 计数器看得见，读题类的 bug 只能靠对拍。
点「运行 ▶」看结果
13 实测：每多一组，暴力乘以 4，正解只加 3 件
本机实测（./groupGenBig 组数，固定种子，每组 3 件）：
| 组数 | DFS 暴力 | 三层循环 | 正解要处理的件数 |
|---|---|---|---|
| 10 | 0.006 秒 | 0.004 秒 | 30 |
| 12 | 0.038 秒 | 0.004 秒 | 36 |
| 14 | 0.568 秒 | 0.004 秒 | 42 |
| 15 | 2.399 秒 | 0.004 秒 | 45 |
groupGenBig.cpp 的第一版把容量定死成 2000、重量取 100 ~ 500，
结果 15 组时暴力只要 0.037 秒 —— 快得莫名其妙。
原因是 DFS 里那句 if (it.w <= rest)：装到第五六件就再也装不下了，
那棵 4^组数 的树根本没长出来，等于白送了一个剪枝（第 16 章那三板斧之一）。
改成「容量 = 每组最重那件之和的六成」之后，一大半的组都还装得下，树才真的长开， 15 组从 0.037 秒涨到 2.399 秒。
要对比暴力有多慢，先确认它真的走到底了。 这和第 24 章「只造大 k」是同一类错误的两个面孔。
14 ★ 对拍（二）
300 轮实测，六个错误版本汇总（前三个是二维费用，后三个是分组）：
| 故意写错的地方 | 被抓 | 第几轮 |
|---|---|---|
| 二维费用：外层容量循环正序 | 237 / 300 | 第 2 轮 |
| 二维费用：忘了体积维 | 141 / 300 | 第 2 轮 |
| 二维费用：外层倒序、内层正序 | 0 / 300 | 它是对的 |
| 分组：组内枚举提到容量外 | 249 / 300 | 第 1 轮 |
| 分组：容量循环正序 | 291 / 300 | 第 1 轮 |
| 分组：漏掉「本组不选」 | 92 / 300 | 第 3 轮 |
groupMust.cpp 只在一种局面下露馅：某一组差到宁可整组跳过。
容量一旦宽松，多塞一件哪怕很差的东西也不亏 —— 正解自己也会去拿它，两份代码答案一样。
所以生成器改了三次，每次只动一处，每次都实测：
| 生成器怎么改 | 抓获率 |
|---|---|
最初：容量 W 独立随机 | 24 / 300 |
改成由物品反推 W（背包一定吃紧） | 53 / 300 |
| 「垃圾组」独立掷骰子，出现率从 1/3 提到 1/2 | 65 / 300 |
垃圾组的重量改成按 W 定（每件都吃掉半个背包以上） | 92 / 300 |
抓不住不代表 bug 不存在，只代表你的数据里没有它需要的那个局面。
还有一件事，第 9 步那组手算数据本身就是证据：如果第 4 组（那组「又重又不值钱」的）不存在，
groupMust.cpp 在那组数据上会恰好蒙对（同样是 16）。
默认数据蒙对，300 轮里照样错 92 轮 —— 样例过了，什么都证明不了。
15 这一章可以带走的四样东西
【1】多一维费用 = 多一层循环，别的什么都不用改。
状态多一维、转移下标多一维、循环多一层。方向由「每件能拿几件」决定，
和「有几维费用」没有半点关系 —— 第 24 章那张表原样就能用。
代价是空间 O(WV)：两个上限是乘起来的，所以这类题的上限都开得很小。
【2】二维费用里，只有外层那一维的方向说了算。
因为 f 是按外层下标分成整行的，一行要么整体动过、要么整体没动过。
（口诀仍然建议两层都写倒序 —— 不是因为必须，是因为那样不用每次都想一遍。）
【3】分组背包的三层循环：组 → 容量倒序 → 组内枚举。 组内那层必须在最里面，这样本组的每一件都从「本组还没出手」的同一个局面出发。 写反的两种方式，正好分别是第 23、24 章的正确答案 —— 顺序不是格式，顺序就是题目本身。
【4】对拍抓不住，有两种完全不同的原因，别混为一谈。 一种是它本来就没错（外倒内正，0/300）； 另一种是你的数据里没有它需要的那个局面（体积永远宽松 → 忘了体积维 0/300）。 写完生成器先问一句：我这份数据，能让错误的写法必定失败吗？
第 26 章：区间 DP（石子合并）。
背包三章的状态都是「前 i 个物品 + 剩多少容量」，
下一章的状态换成了一段区间 f[l][r] —— 而它的填表顺序既不是从左到右，也不是从右到左，
而是按区间长度从小到大。理由和这一章一模一样：长区间要读短区间的值，
所以短的必须先算好。
「依赖谁，就先填谁」（第 21 章那句话）第四次登场。
16 自测
- 洛谷 P1855 榨取kkksc03 —— 二维费用裸题（钱和时间两个上限）。注意两个上限都只有 200 —— 这就是本章第 7 步说的那个信号
- 洛谷 P1507 NASA的食物计划 —— 同样是二维费用（体积和质量），换了张皮。两题对着写一遍，「多一层循环」就再也忘不了
- 洛谷 P1757 通天之分组背包 —— 分组背包模板题。输入是「每件物品自带组号」，先归类再跑 —— 正好练一遍本章那个输入格式的转换
- 洛谷 P1064 金明的预算方案 —— NOIP2006。主件 + 附件，看上去是新题型，其实是分组背包：把「主件单买 / 主件+附件1 / 主件+附件2 / 主件+两个附件」当成一组里的四件互斥物品。★ 这题是「看出它是分组背包」的经典训练
- 洛谷 P1541 乌龟棋 —— NOIP2010。四种卡片各用了几张 → 四维费用，也就是四层循环。本章那句「多一维就多一层」的极致版本
- 洛谷 P5322 排兵布阵 —— BJOI2019。进阶：先想清楚「对第 i 座城堡派 x 个兵能赢几个对手」，再把每座城堡的所有 x 当成一组。适合确认自己是真的会了