背包DP

0-1背包

问题：有 \(n\) 个物品和一个容量为 \(W\) 的背包，每个物品有重量 \(w_i\) 和价值 \(v_i\) 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

每个物品只有取和不取两种选择，所以称为0-1背包问题。

设DP状态\(f_{i,j}\)为只放前\(i\)个物品的情况下，容量为\(j\)的背包可以达到的最大价值。则有：

\[ f_{i,j} = \max(f_{i-1,j}, f_{i-1,j-w_i}+v_i) \]

这样的话状态是一个二维数组，直接的一个优化是观察到\(f_{i,...}\)只和\(f_{i-1,...}\)有关系，所以可以去掉\(i\)这一维，直接在\(f_j\)上面做状态的更新，也就是：

\[ f_j = \max(f_j,f_{j-w_i}+v_i) \]

这样就把状态简化成了一维，节省了大量内存。要注意的是，因为\(f_j\)依赖\(f_k (k \leq j)\)，所以更新\(f_j\)的时候，需要从大到小更新，才能不覆盖后面需要使用到的值。

模板代码:

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]);