合肥seo网站推广费用,企业网站备案名称要求,备案域名租用,网站强制字体wordpress动态规划: 背包DP大合集 背包DP1. 01背包1.1. 问题描述#xff1a;1.2. 状态转移方程1.3. 代码1.4. 空间压缩版本习题 2. 完全背包2.1. 问题描述2.2. 状态转移方程2.3. 代码习题 3. 多重背包3.1. 问题描述#xff1a;3.2. 状态转移方程3.3. 代码(朴素版本)3.4. 代码(二进制优… 动态规划: 背包DP大合集 背包DP1. 01背包1.1. 问题描述1.2. 状态转移方程1.3. 代码1.4. 空间压缩版本习题 2. 完全背包2.1. 问题描述2.2. 状态转移方程2.3. 代码习题 3. 多重背包3.1. 问题描述3.2. 状态转移方程3.3. 代码(朴素版本)3.4. 代码(二进制优化解法)3.5. 为什么二进制拆分有效1数学原理2优化后的时间复杂度 3.6. 复杂度习题 4. 分组背包4.1. 问题描述4.2. 状态转移方程4.3. 代码(朴素版本)4.4. 复杂度4.5. 空间优化版本习题 5. 有依赖的背包5.1. 问题描述5.2. 解法二维DP1状态定义2状态转移3初始化 5.3. 代码5.4. 复杂度分析习题 6. 混合背包6.1. 关于混合背包问题的实现选择习题 背包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(vectorint w, vectorint v, int W) {int n w.size();vectorvectorint dp(n 1, vectorint(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(vectorint w, vectorint v, int W) {int n w.size();vectorint 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(vectorint w, vectorint v, int W) {int n w.size();vectorvectorint dp(n 1, vectorint(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(vectorint w, vectorint v, int W) {int n w.size();vectorint 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. 代码(朴素版本)
直接解法的问题
如果直接枚举每种物品的选取次数 k0 ≤ 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 背包 问题。
vectorint 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 47 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 12 23 1 24 45 1 46 2 47 1 2 48 1 2 4 1但 3 已经覆盖了剩余部分9 2 4 310 1 2 4 3
2优化后的时间复杂度
直接多重背包O(n × W × s)二进制优化后O(n × log(s) × W) 例如 s 1e5log(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() {vectorvectorint dp(n1,vectorint(m1,0));// 遍历组数for(int i 0; in; i){// 遍历背包容量for(int j 1; jm; j){// 不选第i组dp[i1][j] dp[i][j];// 选第i组, 遍历物品for(int k0; kgroup[i].size();k){if(j W[i][k]){dp[i1][j] max(dp[i1][j], dp[i][j-W[i][k]]V[i][k]);}}}}return dp[n][m];
}4.4. 复杂度
时间复杂度: O(物品数量*背包容量)
4.5. 空间优化版本
int knapsackGroup(vectorvectorpairint, int groups, int W) {vectorint 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;vectorItem attachments; // 附件列表
};int dependentKnapsack(vectorItem mains, int W) {int n mains.size();vectorvectorint dp(n 1, vectorint(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; // 背包容量vectorItem items {{3, 5, {{1, 2}, {2, 3}}}, // 主件1w3,v5附件1w1,v2附件2w2,v3{4, 6, {{2, 2}}}, // 主件2w4,v6附件1w2,v2{2, 3, {}} // 主件3w2,v3无附件};int max_value dependentKnapsack(items, W);cout 最大价值: max_value endl; // 输出: 13主件1 附件1 附件2return 0;
}5.4. 复杂度分析
时间复杂度O(n × W × k)其中 k 是附件组合数最多 4 种情况主件、主件附件1、主件附件2、主件附件1附件2。空间复杂度O(n × W)二维DP表。
习题
Luogu P1064
6. 混合背包
6.1. 关于混合背包问题的实现选择
含多重背包的混合背包问题 ✅ 强烈推荐使用空间优化版本一维DP❌ 不建议用未优化的二维DP因为 多重背包的二进制拆分优化天然适合一维DP二维DP在处理多重背包时会有状态转移矛盾同一物品在不同数量下会覆盖dp[i][j]
vectorint dp(V1);
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);}}
}不含多重背包的混合背包仅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
