动态规划: 背包DP大合集

背包DP

1. 01背包

1.1. 问题描述：

给定物品的重量 w[i] 和价值 v[i]，背包容量 W，每种物品只能选 0 或 1 次，求最大价值。

1.2. 状态转移方程

dp[i][j] : 前 i 个物品，背包容量 j 时的最大价值。

转移方式:

• 不选第 i 个物品：dp[i][j] = dp[i-1][j]
• 选第 i 个物品：dp[i][j] = dp[i-1][j-w[i]] + v[i]

最终方程:

dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i])

1.3. 代码

int knapsack01(vector<int>& w, vector<int>& v, int W) {int n = w.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 遍历物品for (int i = 1; i <= n; i++) {// 遍历背包容量for (int j = 1; j <= W; j++) {if (j >= w[i-1]) {dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);} else {dp[i][j] = dp[i-1][j];}}}return dp[n][W];
}

1.4. 空间压缩版本

int knapsack01_optimized(vector<int>& w, vector<int>& v, int W) {int n = w.size();vector<int> dp(W + 1, 0);for (int i = 0; i < n; i++) {for (int j = W; j >= w[i]; j--) {  // 逆序更新dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}}return dp[W];
}

习题

416. 分割等和子集

494. 目标和

2. 完全背包

2.1. 问题描述

物品可以无限次选取，求最大价值。

2.2. 状态转移方程

dp[i][j] ：前 i 个物品，背包容量 j 时的最大价值。

转移方式：

• 不选第 i 个物品：dp[i][j] = dp[i-1][j]
• 选第 i 个物品 : dp[i][j] = dp[i][j - w[i]] + v[i] 注意和0-1背包的区别是i-1

最终方程:

dp[i][j] = max(dp[i-1][j],dp[i][j - w[i]] + v[i])

2.3. 代码

int knapsackComplete(vector<int>& w, vector<int>& v, int W) {int n = w.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));// 遍历物品for (int i = 1; i <= n; i++) {// 遍历背包容量for (int j = 1; j <= W; j++) {if (j >= w[i-1]) {dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1]);  // 区别在这里 , 选择第i个物品} else {dp[i][j] = dp[i-1][j]; // 不选择第i个物品}}}return dp[n][W];
}

空间优化版本

int knapsackComplete_optimized(vector<int>& w, vector<int>& v, int W) {int n = w.size();vector<int> dp(W + 1, 0);for (int i = 0; i < n; i++) {for (int j = w[i]; j <= W; j++) {  // 正序更新dp[j] = max(dp[j], dp[j - w[i]] + v[i]);}}return dp[W];
}

注意: 完全背包采用正序更新, 其余背包问题采用逆序更新

习题

洛谷P1616

322. 零钱兑换

518. 零钱兑换 II

3. 多重背包

3.1. 问题描述：

• 给定 n 种物品，每种物品：
  • 体积 w[i]
  • 价值 v[i]
  • 数量限制 s[i]（最多选 s[i] 次）
• 背包容量 W，求能装的最大价值。

3.2. 状态转移方程

dp[i][j] = max(dp[i-1][j - k*w[i]] + k*v[i]) // k ∈ [0, s[i]]

3.3. 代码(朴素版本)

直接解法的问题：

• 如果直接枚举每种物品的选取次数 k（0 ≤ k ≤ s[i]），时间复杂度为 O(n × W × max(s[i]))，在 s[i] 很大时（如 s[i] = 1e5），会非常低效。

3.4. 代码(二进制优化解法)

优化思路：

• 二进制拆分：将 s[i] 分解为若干个 2 的幂次 的组合，使得 1, 2, 4, ..., 剩余部分 的组合可以表示 0~s[i] 的所有可能取值。
• 这样，每个物品的 s[i] 次选取被拆分成 log(s[i]) 个 新的物品，从而将多重背包转化为 0-1 背包 问题。

vector<int> new_w, new_v;  // 存储拆分后的物品
for (int i = 0; i < w.size(); i++) {int cnt = s[i];  // 当前物品的数量限制for (int k = 1; k <= cnt; k *= 2) {  // 拆分成 1, 2, 4, 8, ...new_w.push_back(w[i] * k);      // 新物品的体积 = w[i] × knew_v.push_back(v[i] * k);      // 新物品的价值 = v[i] × kcnt -= k;                       // 剩余待拆分的数量}if (cnt > 0) {  // 剩余部分（无法用 2^k 表示的部分）new_w.push_back(w[i] * cnt);new_v.push_back(v[i] * cnt);}
}

示例：

• 假设 s[i] = 10，则拆分为 1, 2, 4, 3（因为 1 + 2 + 4 + 3 = 10）。
• 这样，10 可以表示为 1~10 的任意组合（如 5 = 1 + 4，7 = 1 + 2 + 4）。

（2）转化为 0-1 背包

return knapsack01_optimized(new_w, new_v, W);  // 调用 0-1 背包求解

• 拆分后的 new_w 和 new_v 相当于 新的物品列表，每个物品只能选或不选（0-1 背包）。
• 调用 knapsack01_optimized（前面定义的 0-1 背包滚动数组优化版本）求解。

3.5. 为什么二进制拆分有效？

（1）数学原理

• 任何整数 s 可以表示为 1 + 2 + 4 + ... + 剩余部分。
• 例如 s = 10：
  • 拆分为 1, 2, 4, 3。
  • 可以组合出 1~10 的所有数字：
    • 1 = 1
    • 2 = 2
    • 3 = 1 + 2
    • 4 = 4
    • 5 = 1 + 4
    • 6 = 2 + 4
    • 7 = 1 + 2 + 4
    • 8 = 1 + 2 + 4 + 1（但 3 已经覆盖了剩余部分）
    • 9 = 2 + 4 + 3
    • 10 = 1 + 2 + 4 + 3

（2）优化后的时间复杂度

• 直接多重背包：O(n × W × s)
• 二进制优化后：O(n × log(s) × W)
  • 例如 s = 1e5，log(s) ≈ 17，效率提升显著。

3.6. 复杂度

• 二进制拆分 将多重背包转化为 0-1 背包，降低时间复杂度。
• 适用场景：当 s[i] 较大时（如 s[i] ≥ 100），直接枚举会超时，必须优化。
• 对比：

方法	时间复杂度	适用场景
直接多重背包	O(n × W × s)	s 较小（如 s ≤ 100 ）
二进制优化	O(n × log(s) × W)	s 较大（如 s = 1e5 ）

习题

• AcWing 5. 多重背包问题 II
• 洛谷 P1776 宝物筛选

4. 分组背包

4.1. 问题描述

物品被分为多组, 每组物品只能选择一个, 求最大价值

4.2. 状态转移方程

dp[i][j] : 前i组, 背包容量j时的最大价值

转移方式:

• 不要第i组: dp[i][j] = dp[i-1][j]
• 要第i组中的第k个商品: dp[i][j] = dp[i-1][j-w[i][k]] + v[i][k]

最终方程:

dp[i][j] = max(dp[i-1][j],dp[i-1][j - w[i][k]] + v[i][k])

4.3. 代码(朴素版本)

int knapsackGroup() {vector<vector<int>> dp(n+1,vector<int>(m+1,0));// 遍历组数for(int i = 0; i<n; i++){// 遍历背包容量for(int j = 1; j<=m; j++){// 不选第i组dp[i+1][j] = dp[i][j];// 选第i组, 遍历物品for(int k=0; k<group[i].size();k++){if(j > W[i][k]){dp[i+1][j] = max(dp[i+1][j], dp[i][j-W[i][k]]+V[i][k]);}}}}return dp[n][m];
}

4.4. 复杂度

时间复杂度: O(物品数量*背包容量)

4.5. 空间优化版本

int knapsackGroup(vector<vector<pair<int, int>>>& groups, int W) {vector<int> dp(W + 1, 0);for (auto& group : groups) {for (int j = W; j >= 0; j--) {  // 逆序更新for (auto& [w, v] : group) {if (j >= w) {dp[j] = max(dp[j], dp[j - w] + v);}}}}return dp[W];
}

习题

2218. 从栈中取出 K 个硬币的最大面值和

AcWing 9. 分组背包问题

5. 有依赖的背包

5.1. 问题描述

• 有 n 个物品，分为 主件 和 附件。
• 附件 必须和它的 主件 一起购买（不能单独选附件）。
• 每个主件可以有 0~2 个附件。
• 求在容量 W 的背包中能获取的 最大价值。

5.2. 解法（二维DP）

（1）状态定义

• dp[i][j]：表示 前 i 个主件及其附件，在背包容量 j 时的最大价值。

（2）状态转移

• 情况1：不选当前主件 → dp[i][j] = dp[i-1][j]
• 情况2：只选主件 → dp[i][j] = dp[i-1][j - w_main] + v_main
• 情况3：选主件 + 附件1（如果有）→ dp[i][j] = dp[i-1][j - w_main - w_attach1] + v_main + v_attach1
• 情况4：选主件 + 附件2（如果有）→ dp[i][j] = dp[i-1][j - w_main - w_attach2] + v_main + v_attach2
• 情况5：选主件 + 附件1 + 附件2 → dp[i][j] = dp[i-1][j - w_main - w_attach1 - w_attach2] + v_main + v_attach1 + v_attach2

（3）初始化

• dp[0][j] = 0（没有物品可选时，价值为 0）

5.3. 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Item {int w, v;vector<Item> attachments; // 附件列表
};int dependentKnapsack(vector<Item>& mains, int W) {int n = mains.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; i++) {Item& main = mains[i - 1];for (int j = 0; j <= W; j++) {// 情况1：不选当前主件dp[i][j] = dp[i - 1][j];// 情况2：只选主件（如果容量足够）if (j >= main.w) {dp[i][j] = max(dp[i][j], dp[i - 1][j - main.w] + main.v);}// 情况3：选主件 + 附件1（如果有附件1且容量足够）if (main.attachments.size() >= 1 && j >= main.w + main.attachments[0].w) {dp[i][j] = max(dp[i][j], dp[i - 1][j - main.w - main.attachments[0].w] + main.v + main.attachments[0].v);}// 情况4：选主件 + 附件2（如果有附件2且容量足够）if (main.attachments.size() >= 2 && j >= main.w + main.attachments[1].w) {dp[i][j] = max(dp[i][j], dp[i - 1][j - main.w - main.attachments[1].w] + main.v + main.attachments[1].v);}// 情况5：选主件 + 附件1 + 附件2（如果都有且容量足够）if (main.attachments.size() >= 2 && j >= main.w + main.attachments[0].w + main.attachments[1].w) {dp[i][j] = max(dp[i][j], dp[i - 1][j - main.w - main.attachments[0].w - main.attachments[1].w] + main.v + main.attachments[0].v + main.attachments[1].v);}}}return dp[n][W];
}int main() {int W = 10; // 背包容量vector<Item> items = {{3, 5, {{1, 2}, {2, 3}}}, // 主件1（w=3,v=5），附件1（w=1,v=2），附件2（w=2,v=3）{4, 6, {{2, 2}}},         // 主件2（w=4,v=6），附件1（w=2,v=2）{2, 3, {}}                // 主件3（w=2,v=3），无附件};int max_value = dependentKnapsack(items, W);cout << "最大价值: " << max_value << endl; // 输出: 13（主件1 + 附件1 + 附件2）return 0;
}

5.4. 复杂度分析

• 时间复杂度：O(n × W × k)，其中 k 是附件组合数（最多 4 种情况：主件、主件+附件1、主件+附件2、主件+附件1+附件2）。
• 空间复杂度：O(n × W)（二维DP表）。

习题

Luogu P1064

6. 混合背包

6.1. 关于混合背包问题的实现选择：

1. 含多重背包的混合背包问题：
   • ✅ 强烈推荐使用空间优化版本（一维DP）
   • ❌ 不建议用未优化的二维DP，因为：
     • 多重背包的二进制拆分优化天然适合一维DP
     • 二维DP在处理多重背包时会有状态转移矛盾（同一物品在不同数量下会覆盖dp[i][j]）

vector<int> dp(V+1);
for (auto [t, c, p] : items) {if (p == 0) { // 完全背包for (int j = t; j <= V; j++) dp[j] = max(dp[j], dp[j-t] + c);} else { // 01背包或多重背包if (p == 1) p = 1; // 01背包视为特殊的多重背包for (int k = 1; k <= p; k *= 2) { // 二进制拆分int nt = k*t, nc = k*c;for (int j = V; j >= nt; j--)dp[j] = max(dp[j], dp[j-nt] + nc);p -= k;}if (p > 0) { // 处理剩余int nt = p*t, nc = p*c;for (int j = V; j >= nt; j--)dp[j] = max(dp[j], dp[j-nt] + nc);}}
}

2. 不含多重背包的混合背包（仅01背包+完全背包）：
   • ✅ 两种版本都可以使用
   • 二维DP写法示例：

for (int i = 1; i <= N; i++) {if (p[i] == 1) { // 01背包for (int j = V; j >= t[i]; j--)dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + c[i]);} else { // 完全背包for (int j = t[i]; j <= V; j++)dp[i][j] = max(dp[i-1][j], dp[i][j-t[i]] + c[i]);}
}

一维DP写法示例：

for (int i = 1; i <= N; i++) {if (p[i] == 1) { // 01背包for (int j = V; j >= t[i]; j--)dp[j] = max(dp[j], dp[j-t[i]] + c[i]);} else { // 完全背包for (int j = t[i]; j <= V; j++)dp[j] = max(dp[j], dp[j-t[i]] + c[i]);}
}

习题

Luogu P1833 樱花

AcWing 7