＜背包问题＞

背包问题是一类组合优化问题其基本形式是给定一组物品每个物品都有一个重量和一个价值以及一个有限的背包容量目标是在不超过背包容量的前提下选择物品使得背包中的物品价值最大化。动态规划是解决背包问题的常用方法核心思路是“化繁为简”和“避免重复计算”根据物品选择的限制条件不同分为以下几种经典模型01背包每种物品数量为1只能选择拿1或不拿0。题目一个旅行者有一个最多能用m公斤的背包现在有n件物品它们的重量分别是W1W2...,Wn它们的价值分别为C1,C2,...,Cn。若每种物品只有一件求旅行者能获得最大总价值。思路每个物品都有两种选择选与不选。无序变有序依次考虑前1、2、3……个物品背包容量也考虑连续状态。定义dp[i][j]表示前i件物品在背包容量为j时背包的最大总价值。代码#includeiostream #includevector using namespace std; int main(){ int m,n; cinmn; vectorintw(n1); vectorintv(n1); for(int i1;in;i){ cinw[i]v[i]; } // 定义dp[i][j]前i件物品在背包容量为j时背包的最大总价值 int dp[31][201]{0}; for(int i1;in;i){ //遍历每件物品 for(int j1;jm;j){ //遍历可能的背包容量 if(jw[i]){ // 如果能装入当前物品 dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]v[i]); }else{ dp[i][j]dp[i-1][j]; } } } coutdp[n][m]; return 0; }还可以用一维数组优化空间时间复杂度还是一样都是n*v每次都在同一个一维数组上操作。定义dp[j]表示前i件物品在容量为j时背包的最大总价值。从大到小遍历不能从小到大遍历不然会重复多次放入同一物品背包容量若不放当前物品则dp为上一次值前i-1个物品若放dp为dp[j-w[i]]v[i]。代码#includeiostream #includevector using namespace std; int main(){ int m,n; cinmn; vectorintw(n1); vectorintv(n1); for(int i1;in;i){ cinw[i]v[i]; } // 定义dp[j]前i个物品在背包容量为j时背包的最大总价值 int dp[201]{0}; for(int i1;in;i){ // 遍历每件物品 for(int jm;jw[i];j--){ // 注意注意从大到小遍历背包容量jc[i]肯定不能放i还是上一次结果 dp[j]max(dp[j],dp[j-w[i]]v[i]); } } coutdp[m]; return 0; }完全背包每种物品有无限个可以拿任意数量题目设有n种物品每种物品有一个重量及一个价值每种物品的数量是无限的。同时有一个背包最大载重量为M今从n种物品中选取若干件(同一种物品可以多次选取)使其重量的和小于等于M而价值的和为最大。思路在01背包的一维数组优化空间解法中我提到 “ 注意注意从大到小遍历背包容量 ”以此来防止重复多次放入同一物品而完全背包刚好就是可以重复选择同一物品来使价值最大化那么我们从小到大遍历背包容量则就满足完全背包题目的目标了。代码#includeiostream #includevector using namespace std; int main(){ int m,n; cinmn; vectorintw(n1); vectorintv(n1); for(int i1;in;i){ cinw[i]v[i]; } // 定义dp[j]前i个物品在背包容量为j时背包的最大总价值 int dp[201]{0}; for(int i1;in;i){ // 遍历每件物品 for(int jw[i];jm;j){ // 遍历背包容量 dp[j]max(dp[j],dp[j-w[i]]v[i]); } } coutdp[m]; return 0; }多重背包每种物品有固定数量限制题目第一行两个数n(n500)m(m6000)其中n代表希望购买的奖品的种数m表示拨款金额。接下来n行每行3个数v、w、s分别表示第i种奖品的价格、价值和购买的数量买0件到s件均可其中v100w1000s10。求此次购买能获得的最大的价值。方法一s较小时转换成01背包因为s10我们可以把 s 件拆成 s 个相同物品变成 0-1 背包#includeiostream using namespace std; // dp[i][j]表示前i件商品金额不超过m时的最大价值 int dp[5001][6001]; int cost[5001],val[5001]; int main(){ int n,m,v,w,s; cinnm; int num1; for(int i1;in;i){ cinvws; while(s--){ cost[num]v; val[num]w; num; } } num--; for(int i1;inum;i){ for(int j1;jm;j){ if(jcost[i]){ dp[i][j]max(dp[i-1][j],dp[i-1][j-cost[i]]val[i]); }else{ dp[i][j]dp[i-1][j]; } } } coutdp[num][m]; return 0; }方法二朴素多重背包还是枚举遍历每种物品 → 倒序遍历背包容量 → 枚举当前物品选几件#includeiostream using namespace std; // dp[j]金额不超过j时的最大价值 int dp[6001]; int main(){ int n,m; cinnm; // 遍历每一种物品 for(int i1;in;i){ int v,w,s; cinvws; // 倒序遍历容量避免重复多选同一件 for(int jm;jv;j--){ // 枚举当前物品选1-s件 for(int k1;ks;k){ // 钱够买k件才更新 if(jk*v){ dp[j]max(dp[j],dp[j-k*v]k*w); } } } } coutdp[m]; return 0; }方法三二进制优化s较大时任何一个正整数s都能用1、2、4、8、16...2的幂次组合出来最多买7件分成1件、2件、4件三包任选组合就能买0~7个奖品0件啥都不拿1件1件2件2件3件1件2件4件4件5件1件4件6件2件4件7件1件2件4件s件 → log₂s 包s越大二进制优化省的数量越多核心步骤对每一种物品把最大数量s拆分成若干个 2 的幂次 剩余数如 1,2,4,2每一个幂次打包成一个大物品比如2个一包价格2×v价值2×w4个一包价格4*v价值4*w......对所有大物品跑标准 01 背包#includeiostream using namespace std; // dp[j]金额不超过j时的最大价值 int dp[6001]; int main(){ int n,m; cinnm; for(int i1;in;i){ int v,w,s; cinvws; // 拆分成2的幂次打包 for(int k1;s0;k1){ // 不能超过剩下的数量 int cntmin(s,k); int costcnt*v,valuecnt*w; // 01背包倒序遍历容量 for(int jm;jcost;j--){ dp[j]max(dp[j],dp[j-cost]value); } s-cnt; } } coutdp[m]; return 0; }混合背包01 背包 完全背包 多重背包 三种类型混在一起有的物品只可以取一次有的物品可以取无限次有的物品可以取的次数有一个上限题目一个旅行者有一个最多能用V公斤的背包现在有n件物品它们的重量分别是W1W2...,Wn它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次有的物品可以取无限次有的物品可以取的次数有一个上限。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量且价值总和最大。思路对每个物品分情况处理p0→ 完全背包无限拿正序遍历容量p≥1→ 多重背包有限拿二进制优化 倒序遍历容量代码#includeiostream using namespace std; // dp[j]背包容量不超过j时的最大价值 int dp[201]; int main(){ int v,n,w,c,p; cinvn; for(int i1;in;i){ cinwcp; // 完全背包 if(p0){ for(int jw;jv;j){ dp[j]max(dp[j],dp[j-w]c); } } // 多重背包 else{ for(int k1;p0;k1){ int cntmin(p,k); int weightcnt*w,valuecnt*c; for(int jv;jweight;j--){ dp[j]max(dp[j],dp[j-weight]value); } p-cnt; } } } coutdp[v]; return 0; }分组背包给定n组物品第i组物品包含若干个物品每个物品的重量和价值不同每组最多只能选择一个物品题目金明的预算方案NC16671思路每个主件最多有2个附件那么可以将每个主件与其附件看作一个物品组每个物品组里有只有一个主件一个主件第一个附件一个主件第二个附件一个主件第一个附件第二个附件这四个物品每个物品组只能选一个物品。题目就是分组背包的形式了分组背包解法定义dp[j]表示在背包容量为 j 时的最大价值一维数组优化对于每组物品尝试选择该组中的每一个物品或不选择任何物品更新dp数组代码#include iostream #include vector using namespace std; pairint,inta[60]; //存储每组主件的v,w vectorpairint,int b[60]; //存储每组主件的附件v,w 二维数组 int dp[32010]; //存储前i件物品,总钱数为j时价格*重要度的最大值 int main(){ int n,m,i,v,w,p; cinnm; for(i1;im;i){ //遍历所有物品 cinvwp; wv*w; //更新重要度为价格*重要度 if(p0){ //是主件 a[i]{v,w}; }else{ b[p].push_back({v,w}); //加入所属主件的附件列表 } } for(i1;im;i){ //遍历所有物品 if(a[i].first0) continue; //没有主件 for(int jn;ja[i].first;j--){ //从大到小遍历总钱数 dp[j]max(dp[j],dp[j-a[i].first]a[i].second); //只有一个主件 if(b[i].size()1){ //只有一个附件 if(ja[i].firstb[i][0].first) //可以买主件附件 dp[j]max(dp[j],dp[j-a[i].first-b[i][0].first]a[i].secondb[i][0].second); } if(b[i].size()2){ if(ja[i].firstb[i][0].first) //可买主件第一件附件 dp[j]max(dp[j],dp[j-a[i].first-b[i][0].first]a[i].secondb[i][0].second); if(ja[i].firstb[i][1].first) dp[j]max(dp[j],dp[j-a[i].first-b[i][1].first]a[i].secondb[i][1].second); if(ja[i].firstb[i][0].firstb[i][1].first) dp[j]max(dp[j],dp[j-a[i].first-b[i][0].first-b[i][1].first]a[i].secondb[i][0].secondb[i][1].second); } } } coutdp[n]; return 0; }变形二维约束 01 背包问题题目有带2种气体的气缸一个为氧气一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。求他完成工作所需气缸的总重的最低限度的是多少输入第一行有2整数m,n1m21,1n79表示氧氮各自需要的量。第二行为整数k1k1000表示气缸的个数。此后的k行每行包括aibici1ai211bi791ci8003整数。这些各自是第i个气缸里的氧和氮的容量及汽缸重量。思路每个气缸只能选或不选01 背包双重限制选用气缸总氧气 ≥ 需求氧、总氮气 ≥ 需求氮目标满足气量要求下所选气缸总重量最小定义dp[i][j]为凑出至少 i 升氧、至少 j 升氮的最小气缸总重量。遍历每个气缸倒序更新二维背包避免重复选取同一气缸。#includeiostream using namespace std; const int INF 0x3f3f3f3f; int main(){ int m,n,k,a,b,c; cinmnk; // 定义dp[i][j]至少i升氧、j升氮的最小气缸重量 int dp[22][80]; // 初始化为无穷大 没有气缸凑不出来 for(int i0;im;i){ for(int j0;jn;j){ dp[i][j]INF; } } dp[0][0]0; // 遍历每个气缸执行01背包状态转移 for(int i1;ik;i){ cinabc; for(int xm;x0;x--){ for(int yn;y0;y--){ // 能凑出来才用来更新最优重量 if(dp[x][y]!INF){ // 新的氧气封顶就够了 int omin(xa,m); // 新的氮气 int nimin(yb,n); dp[o][ni]min(dp[o][ni],dp[x][y]c); } } } } coutdp[m][n]; return 0; }