引入
在具体讲何为「背包 dp」前，先来看如下的例题：
有 \(n\) 个物品和一个容量为 \(W\) 的背包，每个物品有重量 \(w_{i}\) 和价值 \(v_{i}\) 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
例题中已知条件有第 \(i\) 个物品的重量 \(w_{i}\) ，价值 \(v_{i}\) ，以及背包的总容量 \(W\) 。
设 DP 状态 \(f_{i,j}\) 为在只能放前 \(i\) 个物品的情况下，容量为 \(j\) 的背包所能达到的最大总价值。
考虑转移。假设当前已经处理好了前 \(i-1\) 个物品的所有状态，那么对于第 \(i\) 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 \(f_{i-1,j}\) ；当其放入背包时，背包的剩余容量会减小 \(w_{i}\) ，背包中物品的总价值会增大 \(v_{i}\) ，故这种情况的最大价值为 \(f_{i-1,j-w_{i}}+v_{i}\) 。
由此可以得出状态转移方程：
这里如果直接采用二维数组对状态进行记录，会出现 MLE。可以考虑改用滚动数组的形式来优化。
由于对 \(f_i\) 有影响的只有 \(f_{i-1}\) ，可以去掉第一维，直接用 \(f_{i}\) 来表示处理到当前物品时背包容量为 \(i\) 的最大价值，得出以下方程：
请读者务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的
实现
在讲解正解之前，请先看笔者写的一段错误代码
for (int l = 0; l <= W - w[i]; l++)
f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);
这段代码哪里错了呢？枚举顺序错了。
仔细观察代码可以发现：对于当前处理的物品 \(i\) 和当前状态\(f_{i,j}\) ，在 \(j\geqslant w_{i}\) 时， \(f_{i,j}\) 是会被 \(f_{i,j-w_{i}}\)所影响的。这就相当于物品 \(i\) 可以多次被放入背包，与题意不符。（事实上，这其实是完全背包问题的解法）
为了避免这种情况发生，我们可以改变枚举的顺序，从 \(W\) 枚举到 \(w_{i}\) ，这样就不会出现上述的错误，因为 \(f_{i,j}\) 总是在 \(f_{i,j-w_{i}}\) 前被更新。
因此正解代码为
for (int i = 1; i <= n; i++)
for (int l = W; l >= w[i]; l--)
f[l] = max(f[l], f[l - w[i]] + v[i]);