背包问题 · 考级冲刺

给定背包容量 $W$ ，每件物品有重量 $w_{i}$ 和价值 $v_{i}$ ，每件只能拿一次，问不超重的前提下价值最大——这就是 01 背包。它是所有 DP 模型里最该背熟的一个，很多题（凑硬币、能否装满、分成两半）都是它的变形。状态定为 $f [i] [j]$ ：只考虑前 $i$ 件物品、容量为 $j$ 时的最大价值。对第 $i$ 件，就两个选择——不拿，或拿。

for (int i = 1; i <= n; i++)
    for (int j = 0; j <= W; j++) {
        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]);
    }
cout << f[n][W];

复杂度 $O (nW)$ 。注意这里 $W$ 是容量、不是物品数，若 $W$ 很大（比如 $1 0^{9}$ ）就不能用这个方法。区分好："每件拿一次"是 01 背包，"每件可拿无限次"是完全背包，方程只差一点，别记混。