第 23 章你亲手确认过一件事：01 背包的一维循环写成正序，
跑出来的不是垃圾，而是完全背包的正确答案 ——
wrong.cpp 和 complete.cpp 拿 300 组数据跑，输出一模一样，一组不差。
所以这一章的第一句话是：完全背包的代码，你已经写出来了。
那还有什么可讲的？两件事，而且都比「改个方向」重要得多：
- 为什么正序是对的 —— 光记住方向，题目一变形你就再也推不回来。 这一章会从二维推一遍，你会看到那层「第 i 种拿几件」的循环是怎么被砍掉的。
- 件数有上限怎么办（多重背包：第 i 种最多
k件）。 这是本章第二个 ★，答案是一个很漂亮的技巧：二进制拆分。
1 一句话问题：三种背包的区别只有一句话
物品都是「价值 v、重量 w」，背包容量 W，求最大总价值。三种题型的差别只在每种能拿几件：
| 题型 | 每种最多拿几件 | 这一章 |
|---|---|---|
| 01 背包 | 1 件 | 第 23 章 |
| 完全背包 | 无限件 | ★ 前半章 |
| 多重背包 | k[i] 件（题目给的） | ★ 后半章 |
01 ≤ 多重 ≤ 完全。
多重背包夹在中间：k = 1 时它退化成 01 背包，k 大到「反正也装不完」时它退化成完全背包。
这个结构后面会用到三次 —— 检查代码、设计数据、debug 的时候都用得上。
2 先用手算一遍：同一组物品，三个答案
容量 W = 12
① 价值 7，重 4
② 价值 5，重 3
③ 价值 3，重 2- 01 背包（每种最多 1 件）：①+②+③ = 重 4+3+2 = 9，价值 15。装不下更多了 → 15
- 多重背包（假设 ① 最多 2 件，②③ 各 1 件）：①×2 + ② = 重 4+4+3 = 11，价值 7+7+5 = 19
- 完全背包（无限件）：①×3 = 重 12，价值 21
15 → 19 → 21，同一批物品，只因为「能拿几件」不同。这三个数后面每一步都会回来验。
3 暴力：DFS 枚举「第 i 种拿几件」
点「运行 ▶」看结果
第 23 章的 2ⁿ 枚举子集在这里不够用了：「拿或不拿」只有两个分支，
而这里每种物品的分支数是 W / w[i] + 1，各不相同。
它慢得离谱，但绝对不会错 —— 这一章前半段的标准答案就是它。
4 第一版 DP：把「拿几件」直接写进转移
照着第 23 章的套路改，最自然的写法就是把 k 塞进转移：
f[i][j] = max{ f[i-1][j - k*w[i]] + k*v[i] } k = 0, 1, 2, ... 只要装得下点「运行 ▶」看结果
它是对的（后面会用 300 组数据验），但多了一层循环：
O(n × W × W/w)，最坏 O(nW²)。W = 40000 时这个平方就要了命。
5 ★ 关键一步（一）：那层循环可以整个砍掉
盯住朴素转移里被枚举的那一排来源：f[i-1][j]、f[i-1][j-w]、f[i-1][j-2w]、f[i-1][j-3w]……
现在把它们按「第 i 种拿了几件」分成两类：
- 一件都不拿：
f[i-1][j]。就一个。 - 至少拿一件：先放一件进去（花掉
w、赚到v），剩下的容量j-w里 第i种还可以继续拿 —— 而「前i种物品、容量j-w、第i种随便拿」 这件事，正好就是f[i][j-w]的定义！
★ 于是：
f[i][j] = max( f[i-1][j], f[i][j-w[i]] + v[i] )
↑↑↑ 第一维是 i，不是 i-1「拿 2 件、3 件、4 件……」全都递归地藏在 f[i][j-w] 里面了，
因为那一格自己也是这么算出来的。一层循环，凭空消失。
⚠ 请把它和第 23 章那句铁律并排放：
| 转移右边的第一维 | 因为 | |
|---|---|---|
| 01 背包（第 23 章） | 必须是 i-1 | 每件最多一件，不能从「已经考虑过它」的局面再拿 |
| 完全背包（本章） | 就是 i | 每件想拿几件拿几件，从「已经拿过它」的局面继续拿正合适 |
是题目决定写 i 还是 i-1。倒序 / 正序只是它在一维下的写法，不是两条要背的口诀。
6 动画：来源从「一整排」塌缩成「两格」
下拉框切换两种写法，只看画面上那个累计查看的来源格数：
默认数据（就是第 23 章那 4 件物品，W = 9）上，朴素要看 85 个格子，优化之后只要 66 个。
差距是 W / (2w) 这个量级。W = 9 太小，看起来只差一点点；
但 W 一大，朴素那边的每一格都要看几百上千个来源，而优化后永远只看两格。
第 9 步的实测表会让你看到真实的差距。
红色那一格（同一行的 f[i][j-w]）才是这个动画真正要你记住的东西：
第 23 章不许它出现，这一章非它不可。
7 压成一维：这就是你上一章写出来的那三行
二维压一维，问的还是第 23 章那个问题：读 f[j-w] 时，读到的是「上一行」还是「这一行」？
只不过这次我们想要读到这一行（因为转移右边就是 i）—— 所以 j 从小到大，正序。
点「运行 ▶」看结果
| 一维循环方向 | 读到的 f[j−w] 是 | 每种能拿几件 | |
|---|---|---|---|
| 01 背包 | j = W → w[i]（倒序） | 上一行的 | 最多 1 件 |
| 完全背包 | j = w[i] → W（正序） | 这一行的 | 无限件 |
其余部分一个字符都不差。你可以把 full.cpp 和第 23 章的 fast.cpp 并排打开对一遍。
8 ★ 反过来也成立：完全背包写成倒序，就变回了 01 背包
点「运行 ▶」看结果
上面这份跑出来是 15 —— 正是第 2 步手算的01 背包答案。
第 23 章：01 背包写成正序 → 得到完全背包的正确答案（300 组一模一样）。 本章 ：完全背包写成倒序 → 得到 01 背包的正确答案（300 组一模一样）。
check:viz 把后一条也钉死了：fullWrong.cpp 和第 23 章那份 fast.cpp，
拿 300 组数据跑，输出一组不差。
所以这两句口诀你只需要记住任何一句，另一句是它的反面 —— 忘了就现推。
更好的办法是连口诀都别记，只记「转移右边写 i 还是 i-1」，方向自己会掉出来。
再看一眼第 23 章那组数据（4 件物品，W = 9），三个数字连起来了：
| 跑法 | 答案 | 出处 |
|---|---|---|
第 23 章 fast.cpp（01，倒序） | 14 | 上一章的正确答案 |
第 23 章 wrong.cpp（01 写成正序） | 18 | 上一章的「错误答案」 |
本章 full.cpp（完全背包，正序） | 18 | ← 同一个数 |
本章 fullWrong.cpp（完全写成倒序） | 14 | ← 又转回去了 |
9 实测：砍掉那层循环值多少
本机实测（物品种数固定 n = 200，只改容量 W）：
| W | 朴素 O(nW²) | 正解 O(nW) |
|---|---|---|
| 5 000 | 0.074 秒 | 0.004 秒 |
| 10 000 | 0.273 秒 | 0.004 秒 |
| 20 000 | 1.059 秒 | 0.005 秒 |
| 40 000 | 4.196 秒 | 0.007 秒 |
W 翻倍，朴素的耗时翻四倍（0.273 → 1.059 → 4.196），正解几乎是直线。
10 下半场：件数有上限（多重背包）
题目再变一个字：第 i 种最多只有 k[i] 件。
点「运行 ▶」看结果
输入每行多了一个 k。上面这组就是第 2 步那组数据，跑出来是 19 —— 夹在 15 和 21 中间。
完全背包的正序会让同一种物品被拿无限多次，
它根本没有任何地方能塞下「最多 k 件」这个限制。
后面第 15 步会实测：直接拿完全背包当多重背包用，300 轮里被抓 188 轮。
11 朴素做法：把 k 件摊开成 k 件独立的物品
这个念头一点都不丢人 —— 它是对的，而且转化本身就是正解的地基：
「第
i种最多拿k件」 ≡ 「有k件一模一样的物品，每件最多拿一件」
后面这句就是 01 背包。摊开，然后倒序，一个字都不用改。
点「运行 ▶」看结果
（它会在 [stderr] 里顺带告诉你摊开成了多少件，跟下一步对比用。）
问题只有一个：复杂度是 O(W × Σk[i])。
100 种物品、每种 1000 件、W = 5000 → 五亿格，交上去就是 TLE。
12 ★ 关键一步（二）：二进制拆分
再问一遍：DP 到底需要什么？
它不需要「这是第 3 件还是第 7 件」，它只需要能凑出 0 ~ k 之间的任意件数。 至于是怎么凑出来的，DP 一点都不关心。
而「用最少的堆凑出 0 ~ k 的所有整数」，第 3 章已经回答过了 —— 二进制：
1, 2, 4, 8, ..., 2^(t-1), 余数其中 2^t - 1 ≤ k，最后单独放一堆余数 k - (2^t - 1)（为 0 就不要）。
★ 为什么一定够用（两句话）：
1,2,4,…,2^(t-1)能凑出0 ~ 2^t-1的每一个数（这就是二进制表示）； 再加上余数那一堆，就能凑到k。因为余数≤ 2^t-1，两段接得上，中间不留空。- 而所有堆加起来正好等于 k，所以也凑不出比
k更多的件数 —— 上限也管住了。
于是件数从 k 掉到 ⌈log₂(k+1)⌉。k = 1000 时从 1000 堆变成 10 堆，一百倍。
拆完之后，每一堆当成一件普通物品（价值 t·v、重量 t·w），
因为每堆只能「整堆拿或整堆不拿」—— 那正是 01 背包，倒序照旧。
点「运行 ▶」看结果
13 动画 + 把「一定凑得出」验给你看
动画分两段：先分堆（1、2、4……分不动了把余数单独成一堆）， 然后把 0 ~ k 每一个件数都凑一遍给你看。
改改上面的 k 试试 7（正好是 2³-1，没有余数）和 8（余数是 1），感受一下余数那一堆的作用。
点「运行 ▶」看结果
不给输入就用一组默认的 k。输出：
k 朴素件数 二进制堆数 拆法 零到 k 全能凑出
---- -------- ---------- ------------------------------ ---------------
1 1 1 1 是
7 7 3 1+2+4 是
8 8 4 1+2+4+1 是
13 13 4 1+2+4+6 是
100 100 7 1+2+4+8+16+32+37 是
1000 1000 10 1+2+4+8+16+32+64+128+256+489 是最后一列不是写死的「是」—— split.cpp 对每个 k 都把 0 ~ k 全枚举一遍，
真的用子集和检查每个件数凑不凑得出来。
check:viz 又把整张表和动画那边的拆分逐行对了一次
（堆数、具体拆法、以及那个「是」）。
14 实测：Σk 变成 Σlog k 值多少
本机实测（n = 100、W = 5000 固定，只改件数上限 k）：
| k 上限 | 朴素摊开 | 二进制拆分 | 朴素耗时 | 拆分耗时 |
|---|---|---|---|---|
| 10 | 530 件 | 276 堆 | 0.005 秒 | 0.004 秒 |
| 100 | 5 140 件 | 581 堆 | 0.012 秒 | 0.005 秒 |
| 1 000 | 53 340 件 | 915 堆 | 0.087 秒 | 0.005 秒 |
| 10 000 | 480 340 件 | 1 232 堆 | 0.770 秒 | 0.005 秒 |
| 100 000 | 5 140 340 件 | 1 585 堆 | 8.252 秒 | 0.005 秒 |
k 每涨十倍，朴素那列也涨十倍；而二进制那列每次只多三百来堆（每种物品多 3 ~ 4 堆）。
这就是「乘法」和「对数」的区别。
k 再大也没用 —— 装满整个背包也只能放 W / w[i] 件。所以读入时加一句：
k = min(k, W / w);k = 100000、w = 20、W = 5000 时，k 立刻被压到 250。
这一句同时也解释了完全背包为什么是多重背包的特例：k 无限大，等价于 k = W / w。
15 ★ 对拍（两台）
前半章：完全背包。 标准答案是 DFS 枚举拿几件。
后半章：多重背包。 标准答案同样是 DFS，而不是 multiNaive.cpp ——
那份和 multi.cpp 都是「拆成 01 再 DP」，同一个思路写两遍只能验出打字错误
（第 20 章那条规矩）。
300 轮实测，五种故意写错的版本全被抓住：
| 故意写错的地方 | 被抓 | 第几轮 |
|---|---|---|
| 完全背包写成倒序 | 290 / 300 | 第 1 轮 |
完全背包内层写成 j > w[i]（差一） | 208 / 300 | 第 2 轮 |
| 二进制拆分忘了余数那一堆 | 137 / 300 | 第 1 轮 |
| 二进制拆分不扣 k（堆的总和超过 k） | 79 / 300 | 第 1 轮 |
拿完全背包当多重背包（无视 k 上限） | 188 / 300 | 第 1 轮 |
我把多重背包的生成器改成「只造大 k」（每种都多到装不完），同样跑 300 轮：
| 故意写错的地方 | 正常数据 | 只有大 k 的数据 |
|---|---|---|
| 忘了余数那一堆 | 137 / 300 | 3 / 300 |
| 不扣 k，总和超过 k | 79 / 300 | 0 / 300 |
无视 k 上限 | 188 / 300 | 0 / 300 |
后两个一轮都抓不到。道理很简单：k 大到反正装不完的时候，
多重背包本来就退化成了完全背包 —— 上限写没写对，答案根本没区别。
这是第 7、20、22 章那条规矩的又一次现形，而且这次代价最惨重：
要随机的是「算法依赖的那个东西」。这里依赖的是 k 的大小，不是 n、不是 W。
一个只造大 k 的生成器，跑一万轮也是绿的，交上去就是 WA。
16 这一章可以带走的四样东西
【1】不要记「01 倒序、完全正序」这两句口诀，记转移右边写 i 还是 i-1。
每件最多一件 → 必须 i-1 → 一维倒序；每件随便拿 → 就是 i → 一维正序。
两个方向互为对方的正确解法，忘了任何一句都能从这里推回来。
【2】「枚举拿几件」这层循环，往往可以被一个「同一行的引用」吃掉。
f[i][j-w] 里已经装着「第 i 种再拿几件」的全部情况了。
这个「让状态自己递归地包含更多情况」的手法，在完全背包之外还会反复见到。
【3】需要的不是「哪几件」，而是「能凑出哪些数量」—— 于是二进制。
k 件 → log k 堆。它和第 3 章的二进制枚举、第 28 章的状压是同一族的东西：
把「一个集合」和「一个整数」对应起来。
【4】生成器要打在「算法依赖的那个量」上。
这一章依赖的是 k 的大小。只造大 k，三个真 bug 里有两个一轮都抓不到。
写完生成器先问自己一句：我这份数据，能让错误的写法必定失败吗？
第 25 章：二维费用背包与分组背包。
多一维费用（比如同时限制重量和体积）就多一层循环，方向照旧 ——
到那时你会发现，本章这张「写 i 还是 i-1」的表原样就能用。
分组背包则是另一种限制：「每组至多选一个」，循环顺序不能错 —— 又一个「顺序写反了不报错、只给你错答案」的例子。
再往后：多重背包其实还能做到 O(nW)（单调队列优化），
那要等第 35 章讲完单调队列再回来收这个尾。
17 自测
- 洛谷 P1616 疯狂的采药 —— 完全背包裸题，就是第 23 章 P1048 的完全背包版。两题对着交一遍，方向的差别一辈子忘不了
- 洛谷 P1853 投资的最大效益 —— 完全背包 + 多年滚动。每年跑一次完全背包，本金滚到下一年 —— 「DP 套在循环里」的入门题
- 洛谷 P1776 宝物筛选 —— 多重背包模板题，n·k 大到不拆分必 TLE。二进制拆分的标准练习
- 洛谷 P2347 砝码称重 —— NOIP1996。布尔多重背包（能不能称出某个重量），转移是 f[j] |= f[j-w]。数据小，拆不拆都能过 —— 正好拿来验证「拆完答案不变」
- 洛谷 P1077 摆花 —— NOIP2012。多重背包的方案数版本：max 换成加法、初值 f[0]=1（第 23 章第 12 步那个套路）
- 洛谷 P5365 英雄联盟 —— 进阶。要先看出「买 k 个皮肤的花费」是分组背包/多重的味道，而且答案要开 long long。适合确认自己是真的会了