01 背包

n 每加 1，暴力的时间就翻一倍（0.344 → 1.395 → 5.717 → 11.803，每加 2 就翻四倍）。 而 DP 那一列压根没动 —— 因为它的工作量是 n × W 个格子， n 从 20 涨到 27，格子从 20000 涨到 27000，根本不算涨。

一条是指数，一条是多项式。n = 100 时暴力要 2¹⁰⁰ 步（宇宙年龄不够用）， DP 只要 10 万格，还是眨眼的事。

慢在哪：2ⁿ 个子集里，绝大多数只是「前几件的选择相同、后面不同」的重复劳动。 DP 要做的就是把「前 i 件已经选完之后的局面」归成一类，只算一次。

沿用第 21、22 章的三件套。状态要能回答「做后面的决定还需要知道什么」， 这题需要知道两件事：还剩几件物品没考虑、背包还能装多少。于是两维：

f[i][j] = 只在前 i 件物品里挑、总重量不超过 j 时，能拿到的最大价值

转移用第 21 章那句万能问法 —— 最后一件物品（第 i 件）是拿还是不拿？ 只有两种，都试一遍取大的：

f[i][j] = f[i-1][j]                              // 不拿第 i 件
f[i][j] = max(f[i][j], f[i-1][j - w[i]] + v[i])  // 拿第 i 件（前提 j >= w[i]）

边界：f[0][j] = 0 —— 一件都不挑，价值当然是 0。这一行不用想，白送的。

顺序：i 从小到大（第 i 行依赖第 i-1 行），j 随便。答案在 f[n][W]。

★ 现在盯住转移右边那两个式子：它们的第一维都是 i-1，一个 i 都没有。

这不是巧合，是「每件最多拿一件」这句题意的全部化身： 第 i 件物品只能从还没考虑过它的局面上叠加。 一旦右边出现 f[i][...]，那就是从「已经考虑过第 i 件」的局面再加一件第 i 件 —— 它就被拿了两次。

这一句是整章的地基。后面所有的坑，坑底都是它。

两行也别留了。反正每一格只是「拿自己和 j−w 那格比一比」，就在一行上原地改：

for (int i = 1; i <= n; i++)
    for (long long j = W; j >= w[i]; j--)     // ★ 倒着！
        f[j] = max(f[j], f[j - w[i]] + v[i]);

★ 为什么必须倒着。现在上一行和这一行挤在同一块内存里了， 所以每次读 f[j - w[i]] 都要问一句：这一格现在是「上一行的值」还是「这一行的值」？

j - w[i] 比 j 小，所以答案完全取决于扫描方向：

而 f[i][j-w] 里可能已经装了第 i 件物品 —— 再加一件，它就被拿了第二次、第三次……

倒序不是规定，是「不许出现 f[i][...]」这条铁律在一维下的唯一实现方式。 你现在不需要背它，只需要记得第 5 步那句：转移右边的第一维必须是 i−1。

把 fast.cpp 的倒序改成正序，你得到的不是垃圾，而是一份完全正确的完全背包代码 （完全背包 = 每件物品有无限多件，第 24 章的内容）。

// 01 背包（每件最多一件）
for (long long j = W; j >= w[i]; j--) f[j] = max(f[j], f[j - w[i]] + v[i]);
// 完全背包（每件无限件）
for (long long j = w[i]; j <= W; j++) f[j] = max(f[j], f[j - w[i]] + v[i]);

两份代码逐字符对比，唯一的区别就是 j 的方向。

道理是同一个，只是这回反过来用：正序时 f[j-w] 是本轮已经更新过的值， 也就是「已经考虑过第 i 件」之后的最优解 —— 在它上面再叠一件第 i 件， 正是完全背包想要的「这件还能再拿」。

check:viz 把这件事钉死了：用第 20 章的生成器造 300 组数据， wrong.cpp 和 complete.cpp 的输出 300 组一模一样，一组不差。

-∞ 不是什么魔法数字，它的意思是**「不可达」**。

转移只会从存在的状态转出去（-∞ 再加多少还是极负，永远抢不过别人）， 于是「不可达」这个性质就自动一路传播下去了，最后 f[W] 还是 -∞ 就说明装不满。

同一个套路还会反复出现： 求方案数初值 f[0] = 1 其余 0；求最小价值初值 f[0] = 0 其余 +∞。 转移方程管的是「怎么算」，初值管的是「从哪儿开始、哪些地方压根没有」。

⚠ 实现细节：-∞ 别真写 LLONG_MIN，加上 v[i] 会溢出。写 LLONG_MIN / 4 之类留出余量， 或者干脆判一句「来源不可达就不转移」（exact.cpp 两样都做了）。

第 22 章那个「记 pre 再回溯」的通用套路，在背包这里有个更省事的版本： 什么都不用记，因为二维表本身就是历史。从 f[n][W] 倒着走：

• f[i][j] == f[i-1][j] → 第 i 件没拿，跳到 (i-1, j)
• 否则 → 第 i 件拿了，跳到 (i-1, j - w[i])

而这正好点破了一维写法的代价：它把中间过程全覆盖掉了，没有历史可以回溯。

要最优值 → 一维；要方案 → 老老实实开二维表。 这条规律对所有 DP 都成立，不是背包特有的。

check:viz 对这份代码做的是硬验证：选出的编号不重不越界、总重量 ≤ W、 而且价值之和正好等于第一行那个最大值。只验第一行的话， 「价值对了但方案是编的」这种 bug 一样抓不出来。

【1】转移右边的第一维必须是 i−1。 这是「每件最多拿一件」唯一的技术含义。一维倒序、二维不能写 f[i][j-w]， 都是它的推论。记这一条，别记两条口诀。

【2】先写二维，再压。 直接背一维那三行，你迟早会背错方向；从二维推下来，倒序就是必然结果而不是规定。 考场上写不确定的时候，就在草稿纸上把二维转移写出来，方向自己会跳出来。

【3】「安静地给你错答案」是 DP 最典型的失败方式。 第 21 章填错顺序如此，这一章循环写反也如此：不报错、不崩溃、还经常蒙对。 唯一靠得住的防线是对拍，而且生成器要让「错误直觉」必定失败 —— 这里靠的是「容量小、重量和容量同一量级」。

【4】转移管「怎么算」，初值管「从哪儿开始、哪些状态压根不存在」。 恰好装满用 -∞、方案数用 1、最小值用 +∞ —— 同一个套路，后面每一章都会再用。