背包DP

01背包

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

设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, -)，所以只用一维数组就可以实现。此时需要注意递推的顺序，因为是f(j)依赖f(j-wi)，即后面的值依赖前面的值，所以要从后往前遍历。核心代码：

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

和01背包相似，但是每个物品可以任意多次地被选取。此时

$f_{i, j} = max (f_{i - 1, j}, f_{i, j - w_{i}} + v_{i})$

要想让上述的转移关系成立，就必须让f(i,j-wi)早于f(i,j)被算出，所以此时的递推顺序正好相反。

for (int i = 1; i <= n; i++)
  for (int l = 0; l <= W - w[i]; l++)
    f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);