背包 DP (Knapsack DP)¶
问题原型¶
给定容量为 \(m\) 的背包和 \(n\) 件物品（第 \(i\) 件物品重量为 \(w_i\)，价值为 \(v_i\)），求不超过背包容量的最大价值。
核心思想¶
用 \(dp[i][j]\) 表示在容量为 \(j\) 的背包中，从前 \(i\) 件物品选择装入可达到的最大价值。
依次处理每个物品：
- 若第 \(i\) 件物品不装入背包，则 \(dp[i][j] = dp[i−1][j]\) ；
- 若第 \(i\) 件物品装入背包，则 \(dp[i][j] = dp[i−1][j−w_i] + v_i (j ≥ w_i)\) 。
通过状态转移方程实现从 \(dp[i-1][...]\) 到 \(dp[i][...]\) 的递推更新，最终在 \(dp[n][m]\) 处得到最大价值。
1. 0/1 背包¶
特点：每件物品只能选或不选
状态转移方程：
实现：
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
使用滚动数组简化：
for (int i = 1; i <= n; i++) {
for (int j = m; j >= w[i]; j--) { // 逆序遍历，防止一个物品被重复选取
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
2. 完全背包¶
特点：每件物品可以选无限次
状态转移方程：
实现：
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) { // 正序遍历，循环中可用到本轮已装入该物品的情况
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}
}
使用滚动数组简化：
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) { // 正序遍历，循环中可用到本轮已装入该物品的情况
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
3. 多重背包¶
特点：第 \(i\) 件物品最多选 \(s_i\) 次
思路：若直接循环枚举第 \(i\) 件物品 \(s_i\) 次，容易超时。于是用空间换时间，将 \(s_i\) 拆分为 \(2\) 的幂次，即 \(s_i = 2 ^ 0 + 2 ^ 1 + ... + 2 ^ {\lfloor \log_2(s_i + 1) \rfloor - 1} + o\) 。若 \(s_i + 1\) 是 \(2\) 的整数次幂， \(o = 0\) ；否则 \(o = s_i - 2 ^ {\lfloor \log_2(s_i + 1) \rfloor - 1}\) 。以上拆分可通过组合表示任意 \(≤ s_i\) 个物品的等效选取方式，将问题转化为选/不选拆分后得到的新物品，随后做 0/1 背包即可。
实现：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s[i]; j *= 2) { // 分解为2的幂次
cnt++;
w0[cnt] = w[i] * j;
v0[cnt] = v[i] * j;
s[i] -= j;
}
if (s[i] > 0) { // 处理剩余部分
cnt++;
w0[cnt] = w[i] * s[i];
v0[cnt] = v[i] * s[i];
}
}
// 0/1 背包
for (int i = 1; i <= cnt; i++) {
for (int j = m; j >= w0[i]; j--) { // 逆序遍历，防止一个物品被重复选取
dp[j] = max(dp[j], dp[j - w0[i]] + v0[i]);
}
}
Notes¶
题目涉及的最多的模型还是 0/1 背包，即取 or 不取的问题。主要还是确定如何记录状态，以及列出状态转移方程。此外，更新状态时需注意正序/逆序遍历，防止非法的重复选取。