背包的方程 · 考级冲刺

考虑第 $i$ 件物品，转移只有两支：

$f [i] [j] = max (不拿 f [i - 1] [j], 拿 f [i - 1] [j - w_{i}] + v_{i})$

"不拿"就照抄上一行同一列；"拿"要先从容量里腾出 $w_{i}$ 的空间（去看 $j - w_{i}$ 那一列的最优），再加上它的价值 $v_{i}$ 。关键：拿的那一项引用的是 $f [i - 1]$ ，也就是"还没放过第 $i$ 件"的状态，这样保证每件只被算一次。什么时候"拿"不成立？当 $j < w_{i}$ ，容量根本装不下这件， $j - w_{i}$ 会成为负下标，此时只能不拿。

f[i][j] = f[i-1][j];
if (j >= w[i])
    f[i][j] = max(f[i][j], f[i-1][j - w[i]] + v[i]);

坑一：不判 j >= w[i] 就访问负下标，越界或读到脏数据。坑二：把"拿"写成 f[i][j-w[i]]（同一行），那就变成完全背包、一件被拿多次了。方程记牢：01 背包"拿"的项一定来自上一行。