动态规划--背包九讲

背包九讲详细教程

目录

1. 01背包问题
2. 完全背包问题
3. 多重背包问题
4. 混合背包问题
5. 二维费用背包问题
6. 分组背包问题
7. 有依赖的背包问题
8. 泛化物品
9. 背包问题问法变化

---

1. 01背包问题

问题定义

• 有 N 件物品和容量为 V 的背包，每件物品体积 v[i]，价值 w[i]，每件物品仅可用一次。求背包能装的最大价值。

状态定义

• dp[i][j]：前 i 个物品放入容量为 j 的背包的最大价值。

状态转移方程
$$dp[i][j]=\max (dp[i-1][j],dp[i-1][j-v[i]]+w[i])$$

• 不选第 i 物品：dp[i][j] = dp[i-1][j]
• 选第 i 物品：j ≥ v[i] 时，dp[i][j] = dp[i-1][j - v[i]] + w[i]。

优化：滚动数组

• 一维数组优化：内层循环倒序更新（避免重复使用物品）。

int dp[V+1] = {0}; // V为背包容量for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); }}

初始化细节

• 恰好装满：dp[0]=0，其余初始化为 -∞
• 非装满：全部初始化为 0。

---

2. 完全背包问题

问题定义

• 物品可无限次使用，其余同01背包。

状态转移方程
$$dp[i][j]=\max (dp[i-1][j],dp[i][j-v[i]]+w[i])$$

• 与01背包区别：选物品时用 dp[i][j-v[i]]（同层状态，允许重复选）。

优化：正序遍历

for (int i = 1; i <= N; i++) { for (int j = v[i]; j <= V; j++) { // 正序 dp[j] = max(dp[j], dp[j - v[i]] + w[i]); }}

简单剪枝

• 若物品 i 和 j 满足 v[i] ≤ v[j] 且 w[i] ≥ w[j]，则剔除 j。

---

3. 多重背包问题

问题定义

• 第 i 物品最多用 s[i] 次[citation:5]。

二进制优化

• 将 s[i] 拆成 1, 2, 4, ..., 2^k, c（剩余部分），转化为01背包。

vector<pair<int, int>> items; // (体积, 价值)for (int i = 1; i <= N; i++) { int cnt = s[i]; for (int k = 1; k <= cnt; k *= 2) { items.push_back({k * v[i], k * w[i]}); cnt -= k; } if (cnt > 0) items.push_back({cnt * v[i], cnt * w[i]});}// 再用01背包求解

单调队列优化

• 时间复杂度 O(NV)，适用于 s[i] 极大的情况。

---

4. 混合背包问题

问题定义

• 混合01、完全、多重背包三类物品。
  解法

for (int i = 1; i <= N; i++) { if (s[i] == -1) { // 01背包 for (int j = V; j >= v[i]; j--) dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } else if (s[i] == 0) { // 完全背包 for (int j = v[i]; j <= V; j++) dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } else { // 多重背包（二进制优化） // 先拆包，再做01背包 }}

---

5. 二维费用背包问题

问题定义

• 背包有两种费用 V（体积）和 M（重量），物品消耗两种费用。
  状态转移

for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { for (int k = M; k >= m[i]; k--) { // m[i]为物品重量 dp[j][k] = max(dp[j][k], dp[j - v[i]][k - m[i]] + w[i]); } }}

---

6. 分组背包问题

问题定义

• 物品分为 K 组，每组只能选一个物品。
  状态转移

for (int i = 1; i <= K; i++) { // 遍历组 for (int j = V; j >= 0; j--) { for (int k = 0; k < s[i]; k++) { // 遍历组内物品 if (j >= v[k])  dp[j] = max(dp[j], dp[j - v[k]] + w[k]); } }}

---

7. 有依赖的背包问题

问题定义

• 物品间存在依赖关系（如选子节点必须先选父节点），形成树形结构。
  解法
• 树形DP + 分组背包：
  1. 递归遍历子树，将子树视为分组
  2. 子树分组内物品为子树的不同体积分配方案
  3. 用分组背包更新父节点状态。

---

8. 泛化物品

核心思想

• 将背包问题中的物品抽象为价值函数 h(j)，表示分配 j 容量时该物品的价值。
• 合并两个泛化物品：
  h ( j ) = max ⁡ k = 0 j ( f ( k ) + g ( j − k ) ) h(j) = \\max_{k=0}^{j} (f(k) + g(j - k))h(j)=k=0maxj​(f(k)+g(j−k))

---

9. 背包问题问法变化

常见变体

问法类型 解法 求方案数 用 g[j] 记录方案数 求具体方案 倒推状态转移路径 第K优解 维护前K大值的队列

方案数代码

int dp[V+1] = {0}, g[V+1] = {1}; // g[j]：容量j的方案数for (int i = 1; i <= N; i++) { for (int j = V; j >= v[i]; j--) { int val = dp[j - v[i]] + w[i]; if (val > dp[j]) dp[j] = val, g[j] = g[j - v[i]]; else if (val == dp[j]) g[j] = (g[j] + g[j - v[i]]) % mod; }}

---

关键优化技术总结

技术 适用场景 核心思想 滚动数组 01背包 倒序更新一维数组 二进制拆分 多重背包 将s[i]拆为2^k的组 单调队列 多重背包（大s[i]） 维护滑动窗口最大值 费用提前计算 树形依赖背包 先处理子树再合并到父节点

完整代码示例及细节可参考 DD_engi的背包九讲和 AcWing背包问题解析。