背包问题

Ⅰ. 基础模型

A. 01背包

即每个物品要么选，要么不选。我们可以设状态 $f_{i,j}$ 表示考虑前 $i$ 个物品总体积 $\leq j$ 的最大价值，于是状态转移如下：

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

前一个表示不选第 $i$ 个物品的情况，后一个表示选第 $i$ 个物品的情况。

初始化：$f_{i,j}=0$ 。

考虑怎么统计方案数。状态定义一样，但是表示的是方案数，于是又有转移方程如下：

$$
f_{i,j}=f_{i-1,j}+f_{i-1,j-w_i}
$$

初始化：$f_{i,0}=f_{0,j}=1$ 。

考虑优化空间，我们发现，每次转移只会用到上一维的状态，于是就可以把DP数组压成一维。代码如下：

for (int i = 1; i <= n; i++) {
	for (int j = m; j >= w[i]; j--) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

B. 完全背包

就是在01背包的基础上每个物品可以选任意多个。状态设计同01背包，转移如下：

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

区别在哪里呢？完全背包可以从当前的 $i$ 的状态转移过来，因为一个物品可以一选再选。

初始化、变形成方案数统计和压空间和上面的01背包大同小异，不过多赘述。贴个优化空间代码：

for (int i = 1; i <= n; i++) {
	for (int j = w[i]; j <= m; j++) {
		f[j] = max(f[j], f[j-w[i]]+v[i]);
	}
}

C. 多重背包