01 背包

问题形式

$n$ 种物品，第 $i$ 种重量为 $w_i$，价值为 $v_i$，每种物品只有一个。有一个容量为 $m$ 的背包，让你选择一些物品放进背包，在物品重量和 $\le m$ 的情况下使物品价值和最大。

状态与转移

设 $f_{i, j}$ 为前 $i$ 个物品中选重量和为 $j$ 的物品的最大价值和。

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

优化

滚动数组

我们可以将 $i$ 维舍弃，并对 $j$ 维使用倒序循环（为了不让 $f_{i, j}$ 从 $f_{i, j - v_i}$ 转移）。

完全背包

问题形式

$n$ 种物品，第 $i$ 种重量为 $w_i$，价值为 $v_i$，每种物品有无数个。有一个容量为 $m$ 的背包，让你选择一些物品放进背包，在物品重量和 $\le m$ 的情况下使物品价值和最大。

状态与转移

设 $f_{i, j}$ 为前 $i$ 个物品中选重量和为 $j$ 的物品的最大价值和。

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

优化

滚动数组

我们可以将 $i$ 维舍弃，并对 $j$ 维使用正序循环（为了让 $f_{i, j}$ 从 $f_{i, j - v_i}$ 转移）。

多重背包

$n$ 种物品，第 $i$ 种重量为 $w_i$，价值为 $v_i$，有 $c_i$ 个。有一个容量为 $m$ 的背包，让你选择一些物品放进背包，在物品重量和 $\le m$ 的情况下使物品价值和最大。

最直接的方法是将每一种物品拆成 $c_i$ 个一样的物品然后使用 01 背包，时间复杂度为 $O(m \times \sum c_i)$。

优化

滚动数组

同 01 背包。

二进制拆分

对于每一种物品，设 $p$ 为满足 $\sum_{j = 0}^p 2^j \le c_i$ 的最大值，$l$ 为 $c_i - \sum_{j = 0}^p 2^j$，我们可以将物品拆分为 $(v_i \times 2^0, w_i \times 2^0), (v_i \times 2^1, w_i \times 2^1), \cdots, (v_i \times 2^p, w_i \times 2^p), (v_i \times l, w_i \times l)$。

这样可以保证这 $p + 2$ 个物品可以组成 $1 \sim c_i$ 的所有情况，时间复杂度为 $O(m \times \sum \log c_i)$。

单调队列优化

不优化的转移是这样的：

$f_j = \max_{k = 1}^{c_i}\{f_{j - k \times v_i} + k \times w_i\}$

这个式子很难优化，我们发现 $f_j$ 总是会从 $f_{j - k \times v_i}$ 转移，所以我们可以将 $j$ 按照 $\mod v_i$ 的余数分组，因为不同组之间不会互相影响，所以可以对每一组分别 DP。$j \in [0, v_i)$（代表余数），转移方程变成这样：

$f_{j + k \times v_i} = \max_{l = k - c_i}^{l - 1}\{f_{j + l \times v_i} + (k - l) \times w_i\}$

这样子就可以使用单调队列优化了，时间复杂度为 $O(nm)$。

注意，余数 $j$ 的循环顺序没有影响（每一组不会互相转移），但是 $k$ 必须要倒着循环（原理同 01 背包）。

具体代码实现在这里：

#include <algorithm>
#include <cstdio>

using namespace std;

int n, m, v[1001], w[1001], c[1001], f[20001], ans;
int s, t, q[20001];
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d%d%d", &v[i], &w[i], &c[i]), c[i] = min(c[i], m / v[i]);
	for (int i = 1;i <= n;i ++){
		for (int j = 0;j < v[i];j ++){ // 枚举余数 j
			#define calc(x) (f[j + (x) * v[i]] - (x) * w[i])
			s = 1, t = 0;
			int p = (m - j) / v[i]; // 最大能选取的 k
			for (int k = p - 1;k >= max(p - c[i], 0);k --){
				while (s <= t && calc(q[t]) <= calc(k)) t --;
				q[++ t] = k;
			} // 先将初始决策插入单调队列（k = p 时需要的决策）
			for (int k = p;k >= 0;k --){
				while (s <= t && q[s] > k - 1) s ++; // 删除不合法的决策
				if (s <= t) f[j + k * v[i]] = max(f[j + k * v[i]], calc(q[s]) + w[i] * k); // 转移
				if (k - c[i] - 1 < 0) continue;
				while (s <= t && calc(q[t]) <= calc(k - c[i] - 1)) t --; // 维护单调性
				q[++ t] = k - c[i] - 1; // 插入新决策
			}
		}
	}
	for (int j = 0;j <= m;j ++) ans = max(ans, f[j]);
	printf("%d", ans);
}

分组背包

$n$ 组物品，第 $i$ 组内有 $c_i$ 种物品。第 $i$ 组内第 $j$ 种物品重量为 $w_{i, j}$，价值为 $v_{i, j}$，每种物品只有一个。有一个容量为 $m$ 的背包，让你选择一些物品放进背包，在满足物品重量和 $\le m$ 且每一组物品最多只放一个的情况下使物品价值和最大。

状态与转移

设 $f_{i, j}$ 为前 $i$ 组物品中选重量和为 $j$ 的物品的最大价值和。

$f_{i, j} = \max\begin{cases}f_{i - 1, j}\\ \max_{k = 1}^{c_i} f_{i - 1, j - v_{i, k}} + w_{i, k}\end{cases}$

优化

滚动数组

同 01 背包。