动态规划3——背包类动态规划详解_背包问题
动态规划之背包问题详解
背包问题是动态规划领域的核心内容，也是算法竞赛和面试中的常考题型。本文系统性地介绍各类背包问题的解题思路、状态转移方程和优化技巧，帮助读者全面掌握这一重要算法范式。
一、01背包问题
问题描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
核心思想
01背包的核心在于每件物品只有选与不选两种状态，状态转移方程为：
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])
代码实现
二维解法（基础）
#include #include using namespace std;const int MAXN = 1005;int f[MAXN][MAXN]; // f[i][j]表示前i件物品放入容量为j的背包的最大价值int v[MAXN], w[MAXN]; // 体积和价值int main() { int n, m; cin >> n >> m; for (int i = 1; i > v[i] >> w[i]; for (int i = 1; i <= n; i++) { for (int j = 0; j = v[i]) // 能选第i件物品 f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]); } } cout << f[n][m]; return 0;}
一维优化（空间优化）
#include #include using namespace std;const int MAXN = 1005;int f[MAXN]; // 优化为一维数组int v[MAXN], w[MAXN];int main() { int n, m; cin >> n >> m; for (int i = 1; i > v[i] >> w[i]; for (int i = 1; i = v[i]; j--) // 逆序遍历避免覆盖 f[j] = max(f[j], f[j-v[i]] + w[i]); cout << f[m]; return 0;}
关键点
-
逆序遍历保证每个物品只被选取一次
-
状态转移基于前一个状态的值
-
时间复杂度O(NV)，空间复杂度O(V)
二、完全背包问题
问题描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
核心思想
与01背包的区别在于物品可以无限次选取，状态转移方程为：
f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i])
代码实现
二维解法
#include #include using namespace std;const int MAXN = 1005;int f[MAXN][MAXN];int v[MAXN], w[MAXN];int main() { int n, m; cin >> n >> m; for (int i = 1; i > v[i] >> w[i]; for (int i = 1; i <= n; i++) { for (int j = 0; j = v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]] + w[i]); } } cout << f[n][m]; return 0;}
一维优化
#include #include using namespace std;const int MAXN = 1005;int f[MAXN];int v[MAXN], w[MAXN];int main() { int n, m; cin >> n >> m; for (int i = 1; i > v[i] >> w[i]; for (int i = 1; i <= n; i++) for (int j = v[i]; j <= m; j++) // 正序遍历允许重复选取 f[j] = max(f[j], f[j-v[i]] + w[i]); cout << f[m]; return 0;}
与01背包的区别
-
正序遍历允许物品多次选取
-
状态转移基于当前行而不是上一行
-
时间复杂度仍为O(NV)，但状态转移逻辑不同
三、多重背包问题
问题描述
有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
二进制优化
当物品数量较大时，使用二进制优化将多重背包转化为01背包：
#include #include using namespace std;const int MAXN = 25000; // 1000*log2000 ≈ 22000int f[MAXN], v[MAXN], w[MAXN];int main() { int n, m, cnt = 0; cin >> n >> m; // 二进制拆分 for (int i = 1; i > a >> b >> s; int k = 1; while (k 0) { cnt++; v[cnt] = a * s; w[cnt] = b * s; } } // 01背包求解 for (int i = 1; i = v[i]; j--) f[j] = max(f[j], f[j-v[i]] + w[i]); cout << f[m]; return 0;}
优化原理
-
将数量s拆分为2的幂次之和（1,2,4,...,2^k,s-2^k）
-
每个拆分后的物品视为独立的01背包物品
-
优化时间复杂度从O(NVS)降为O(NVlogS)
四、分组背包问题
问题描述
给定N组物品和一个容量为V的背包。每组物品有若干个，但在同一组内，最多只能选择一件物品。每件物品有其对应的体积和价值。目标是选择物品放入背包，使得总体积不超过背包容量，且总价值最大。
状态转移
f[i][j] = max(f[i-1][j], max_{1≤k≤s_i}(f[i-1][j-v_{ik}] + w_{ik}))
代码实现
#include #include using namespace std;const int MAXN = 105;int f[MAXN][MAXN], v[MAXN][MAXN], w[MAXN][MAXN], s[MAXN];int main() { int n, m; cin >> n >> m; for (int i = 1; i > s[i]; for (int j = 1; j > v[i][j] >> w[i][j]; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= m; j++) { f[i][j] = f[i-1][j]; // 不选该组任何物品 for (int k = 1; k = v[i][k]) f[i][j] = max(f[i][j], f[i-1][j-v[i][k]] + w[i][k]); } } } cout << f[n][m]; return 0;}
优化技巧
-
使用一维数组优化空间
-
每组内部循环放在最内层
-
逆序遍历背包容量
五、二维费用背包问题
问题特点
背包限制条件从单一容量变为两个维度（如重量和体积、金钱和时间等）
潜水员问题
#include #include #include using namespace std;const int MAXM = 85, MAXN = 25;int f[MAXM][MAXN]; // f[j][k]: 氧气至少j，氮气至少k的最小重量int O2[MAXN], N2[MAXN], W[MAXN];int main() { int m, n, k; cin >> m >> n >> k; memset(f, 0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i > O2[i] >> N2[i] >> W[i]; for (int i = 1; i = 0; j--) { for (int k = n; k >= 0; k--) { int nj = max(0, j - O2[i]); int nk = max(0, k - N2[i]); f[j][k] = min(f[j][k], f[nj][nk] + W[i]); } } } cout << f[m][n]; return 0;}
宠物小精灵收服
#include #include using namespace std;const int MAXM = 505, MAXN = 1005;int f[MAXN][MAXM]; // f[j][k]: 使用j个球，消耗k体力的最大收服数int balls[MAXN], damage[MAXM];int main() { int n, m, k; cin >> n >> m >> k; m--; // 保留1点体力 for (int i = 1; i > balls[i] >> damage[i]; for (int i = 1; i = balls[i]; j--) { for (int k = m; k >= damage[i]; k--) { f[j][k] = max(f[j][k], f[j-balls[i]][k-damage[i]] + 1); } } } int max_catch = f[n][m], min_damage = 0; for (int k = 0; k <= m; k++) { if (f[n][k] == max_catch) { min_damage = k; break; } } cout << max_catch << \" \" << m + 1 - min_damage; return 0;}
六、混合背包问题
问题描述
混合背包结合了01背包、完全背包和多重背包，需要根据物品类型选择不同的处理策略。
通用解法
#include #include using namespace std;const int MAXM = 205;int dp[MAXM];// 01背包处理void zeroOnePack(int weight, int value, int capacity) { for (int j = capacity; j >= weight; j--) dp[j] = max(dp[j], dp[j-weight] + value);}// 完全背包处理void completePack(int weight, int value, int capacity) { for (int j = weight; j = capacity) { completePack(weight, value, capacity); return; } int k = 1; while (k > m >> n; for (int i = 0; i > w >> v >> s; if (s == 0) completePack(w, v, m); else if (s == 1) zeroOnePack(w, v, m); else multiplePack(w, v, s, m); } cout << dp[m]; return 0;}
七、有依赖的背包问题
金明的预算方案
#include #include using namespace std;const int MAXN = 32005;int main_w[65], main_v[65];int annex_w[65][3], annex_v[65][3];int f[MAXN];int main() { int n, m; cin >> n >> m; for (int i = 1; i > v >> p >> q; if (!q) { main_w[i] = v; main_v[i] = v * p; } else { annex_w[q][0]++; annex_w[q][annex_w[q][0]] = v; annex_v[q][annex_w[q][0]] = v * p; } } for (int i = 1; i = main_w[i]; j--) { // 只选主件 f[j] = max(f[j], f[j-main_w[i]] + main_v[i]); // 主件+附件1 if (j >= main_w[i] + annex_w[i][1]) f[j] = max(f[j], f[j-main_w[i]-annex_w[i][1]] + main_v[i] + annex_v[i][1]); // 主件+附件2 if (j >= main_w[i] + annex_w[i][2]) f[j] = max(f[j], f[j-main_w[i]-annex_w[i][2]] + main_v[i] + annex_v[i][2]); // 主件+附件1+附件2 if (j >= main_w[i] + annex_w[i][1] + annex_w[i][2]) f[j] = max(f[j], f[j-main_w[i]-annex_w[i][1]-annex_w[i][2]] + main_v[i] + annex_v[i][1] + annex_v[i][2]); } } cout << f[n]; return 0;}
八、总结与拓展
1.背包问题通用解法框架
-
定义状态：明确dp数组的含义
-
初始化状态：处理边界条件
-
状态转移：根据问题类型选择合适的转移方程
-
确定结果：找到最终状态对应的解
2.优化技巧对比
3.实际应用场景
-
资源分配问题
-
投资组合优化
-
生产计划制定
-
货物装载优化
-
时间管理调度
