01 背包

给定 $n$ 个物品，第 $i$ 个物品价值为 $c[i]$, 体积为 $w[i]$。现有容积为 $m$ 的背包，求将物品装入背包得到的最大价值。

$f[i,v]$: 从前 $i$ 个物品中，选出总体积为 $v$ 的物品，能得到的最大价值。

• 不选第 $i$ 个物品：$f[i,v]=f[i-1,v]$；
• 选第 $i$ 个物品：$f[i,v]=f[i-1,v-w_i]+c_i$。

$$f[i,v]=max\{\begin{array}{rl}& f[i-1,v]\\ & f[i-1,v-w_i]+c_i(v\ge w_i)\end{array}$$

问题的解是 $f[n,m]$。时间复杂度：$O(nm)$。

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

空间优化

实际上，状态转移方程的第一维可以去掉，即让新状态覆盖旧状态，降低空间开销。

$$f[v]=max\{\begin{array}{rl}& f[v]\\ & f[v-w_i]+c_i(v\ge w_i)\end{array}$$

但在程序中，直接移除第一维会导致错误。令 $w=1,c=2$，执行内层循环，可见错误的根源。

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$f[v-w]+c=2$	$0$	$0$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$f[v-w]+c=4$	$0$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$4$	$f[v-w]+c=6$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$4$	$6$	$f[v-w]+c=8$

在内层循环中，$f[v-w]$ 不能比 $f[v]$ 先更新，否则相当于同一物品被装多次。倒序枚举 $v$ 以解决问题。

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$0$	$0$	$0$	$f[v-w]+c=2$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$0$	$0$	$f[v-w]+c=2$	$2$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$0$	$f[v-w]+c=2$	$2$	$2$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$f[v-w]+c=2$	$2$	$2$	$2$

for (int i = 1; i <= n; i ++)
	for (int v = m; v >= w[i]; v --)    // 倒序枚举
		f[v] = max(f[v], f[v - w[i]] + c[i]);

完全背包

基于 01 背包，每种物品可装无限次。

$f[i,v]$: 从前 $i$ 种物品中，选出总体积为 $v$ 的物品，能得到的最大价值。

• 不选第 $i$ 种物品：$f[i,v]=f[i-1,v]$；
• 多选一个第 $i$ 种物品：$f[i,v]=f[i,v-w_i]+c_i$。

$$f[i,v]=max\{\begin{array}{rl}& f[i-1,v]\\ & f[i,v-w_i]+c_i(v\ge w_i)\end{array}$$

时间复杂度：$O(nm)$。

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

空间优化

参照 01 背包 - 空间优化 中的错误做法：直接移除第一维，并升序枚举 $v$，相当于将同种物品装多次。

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$f[v-w]+c=2$	$0$	$0$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$f[v-w]+c=4$	$0$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$4$	$f[v-w]+c=6$	$0$

$v$	$0$	$1$	$2$	$3$	$4$
$f[v]$	$0$	$2$	$4$	$6$	$f[v-w]+c=8$

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

多重背包

基于 01 背包，第 $i$ 种物品可装 $s_i$ 次。

在内层循环中，分别绑定 $1,2,\cdots s_i$ 个物品作为一个物品，参与 01 背包。

$$f[v]=\underset{k=1,2,\cdots ,s_i}{max}\{\begin{array}{l}f[v]\\ f[v-k\cdot w_i]+k\cdot c_i(v\ge k\cdot w_i)\end{array}$$

时间复杂度：$O(m\sum s_i)$。

for (int i = 1; i <= n; i ++)
	for (int v = m; v >= w[i]; v --)
		for (int k = 0; k <= s[i] && v >= k * w[i]; k ++)
			f[v] = max(f[v], f[v - k * w[i]] + k * c[i]);

二进制优化

• 任意正整数 $n$ 可拆分为 $1,2,4,\cdots ,2^k,n-2^k$（$n-2^k\ge 0$ 且 $k$ 尽量大）；
• 相反，$1,2,4,\cdots ,2^k,n-2^k$ 能且仅能组合出 $[1,n]$ 中的所有整数。

将 $s_i$ 个物品划分为 $\log s_i$ 组，每组分别有 $1,2,4,\cdots ,2^k,s_i-2^k$ 个物品，并绑定每组为一个物品，参与 01 背包。例如，$s_i=15$ 可以拆分为以下 $4$ 组：

组别	$1$	$2$	$3$	$4$
总体积	$w_i$	$2w_i$	$4w_i$	$8w_i$
总价值	$c_i$	$2c_i$	$4c_i$	$8c_i$

此 $4$ 组物品可组合出所有策略（选 $1\cdots 15$ 个物品）。例如要选 $12$ 个物品，则同时选第 $3,4$ 组即可。

时间复杂度：$O(m\sum \log s_i)$。

for (int i = 1; i <= n; i ++) {
	int wi, ci, s;
	cin >> wi >> ci >> s;
	for (int k = 1; k <= s; k *= 2) {
		w[++ cnt] = k * wi, c[cnt] = k * ci;
		s -= k;
	}
	if (s)
		w[++ cnt] = s * wi, c[cnt] = s * ci;
}
for (int i = 1; i <= tot; i ++)
	for (int v = m; v >= w[i]; v --)
		f[v] = max(f[v], f[v - w[i]] + c[i]);

分组背包

背包体积为 $m$，有 $t$ 组物品，第 $k$ 组有 $s_k$ 个，其中第 $i$ 个体积为 $w_{ki}$，价值为 $c_{ki}$。每组只能取走一个物品。求将物品装入背包得到的最大价值。

$f[k,v]$：从前 $k$ 组物品中，选出总体积为 $v$ 的物品，能得到的最大价值。

• 不选第 $k$ 组：$f[k,v]=f[k-1,v]$；
• 选第 $k$ 组：$ f[k,v]=\max_{1\leq i\leq s_k}\ f[k-1,v-w_{ki}]+c_{ki}$。

$$f[k,v]=max\{\begin{array}{rl}& f[k-1,v]\\ & \underset{1\le i\le s_k}{max}f[k-1,v-w_{ki}]+c_{ki}(v\ge w_{ki})\end{array}$$

可以省去第一维。时间复杂度：$O(nm)$。

for (int k = 1; k <= t; k ++)
	for (int v = m; v >= 0; v --)
		for (int i = 1; i <= s[k]; i ++)
			if (v >= w[k][i])
				f[v] = max(f[v],f[v - w[k][i]] + c[k][i]);

二维背包

背包体积为 $V$，承重为 $M$。有 $n$ 个物品，第 $i$ 个体积为 $v_i$，质量为 $m_i$，价值为 $c_i$。求将物品装入背包得到的最大价值。

$f[p,q]$：用体积为 $p$，承重为 $q$ 的背包放物品，能获得的最大总价值。

$$f[p,q]=max\{\begin{array}{rl}& f[p,q]\\ & f[p-v_i,q-m_i]+c_i(p\ge v_i,q\ge m_i)\end{array}$$

时间复杂度为 $O(nVM)$。

for (int i = 1; i <= n; i ++)
	for (int p = V; p >= v[i]; p --)
		for (int q = M; q >= m[i]; q --)
			f[p][q] = max(f[p][q], f[p - v[i]][q - m[i]] + c[i]);

方案总数

基于 01 背包，求将物品放入背包的方案数。

$g[i,v]$：把前 $i$ 个物品（部分或全部）放入体积为 $v$ 的背包的方案总数。

• 不放第 $i$ 个物品：有 $g[i-1,v]$ 种；
• 放第 $i$ 个物品：有 $g[i-1,v-w_i]$ 种。

$$g[i,v]=g[i-1,v]+g[i-1,v-w_i]$$

同样可以省去第一维：

$$g[v]=g[v]+g[v-w_i](v\ge w_i)$$

初始条件：$g[0]=1$。因为当背包体积为 $0$ 时只有一个方案：不放任何物品。

g[0] = 1;
for (int i = 1; i <= n; i ++)
	for (int v = m; v >= w[i]; v --)
		g[v] += g[v - w[i]];

最优方案总数

基于 01 背包，求最优方案数。

已知 01 背包 的状态转移方程：

$$f[i,v]=max\{\begin{array}{rl}& f[i-1,v]\\ & f[i-1,v-w_i]+c_i(v\ge w_i)\end{array}$$

$g[i,v]$：把前 $i$ 个物品（部分或全部）放入体积为 $v$ 的背包的最优方案数。

• 若 $f[i-1,v]>f[i-1,v-w_i]+c_i$，不放物品 $i$ 最优：$g[i,v]=g[i-1,v]$；
• 若 $f[i-1,v]<f[i-1,v-w_i]+c_i$，放物品 $i$ 最优：$g[i,v]=g[i-1,v-w_i]$；
• 若相等，则两种方案都最优：$g[i,v]=g[i-1,v]+g[i-1,v-w_i]$。

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

省去第一维：

for (int i = 1; i <= n; i ++) {
	for (int v = m; v >= w[i]; v --) {
		int maxn = max(f[v], f[v - w[i]] + c[i]);
		int maxg = 0; // 最优方案数
		if (maxn == f[v])
			maxg += g[v];
		if (maxn == f[v - w[i]] + c[i])
			maxg += g[v - w[i]];
		f[v] = maxn, g[v] = maxg;
	}
}