背包基础篇01、完全、分组、多重、混合问题链接2. 01背包问题 - AcWing题库11. 背包问题求方案数 - AcWing题库12. 背包问题求具体方案 - AcWing题库8. 二维费用的背包问题 - AcWing题库3. 完全背包问题 - AcWing题库9. 分组背包问题 - AcWing题库4. 多重背包问题 I - AcWing题库5. 多重背包问题 II - AcWing题库7. 混合背包问题 - AcWing题库一、01 背包01 背包每件物品只能选一次物品有重量v[i]价值w[i]背包总容量V求最大总价值。1、二维 DP状态定义dp[i][j]前i件物品背包容量为j时的最大价值。转移方程不选第i件d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j]dp[i][j]dp[i−1][j]不选第i件d p [ i ] [ j ] d p [ i − 1 ] [ j − v [ i ] ] w [ i ] dp[i][j]dp[i-1][j-v[i]]w[i]dp[i][j]dp[i−1][j−v[i]]w[i](需要背包容量j大于等于v[i],表示可以装下这个物品 )代码模板#includebits/stdc.h using namespace std; const int N1005; int v1[N],w1[N]; // v1[]重量w1[]价值 int dp[N][N]; // dp[i][j]前i个物品背包容量j的最大价值 int main(){ int n,v; cinnv; // 读入n件物品重量、价值 for(int i1;in;i){ cinv1[i]w1[i]; } // 遍历每件物品 for(int i1;in;i){ // j倒序也能跑但二维推荐正序 for(int jv;j0;j--){ dp[i][j]dp[i-1][j]; // 情况1不选第i件物品 if(v1[i]j) // 背包装得下才可以选 dp[i][j]max(dp[i-1][j],dp[i-1][j-v1[i]]w1[i]); // 取选/不选的最大值 } } coutdp[n][v]; // n件物品容量v的最大答案 return 0; }2、一维 DP二维压缩成一维j 必须倒序遍历防止物品被多次选取如果是正序遍历的话容量是从小的开始的会导致一个物品在放入之后随着容量的增大会被再次放入会变成完全背包问题。状态定义dp[j]容量j背包的最大价值。转移方程d p [ j ] m a x ( d p [ j ] , d p [ j − v [ i ] ] w [ i ] ) dp[j]max(dp[j],dp[j-v[i]]w[i])dp[j]max(dp[j],dp[j−v[i]]w[i])关键点j从总容量V到v[i]倒序代码模板#includebits/stdc.h using namespace std; int main(){ int n,v1; cinnv1; vectorintv(n1),w(n1); for(int i0;in;i){ cinv[i]w[i]; } vectorintdp(v11); for(int i0;in;i){ for(int jv1;jv[i];j--){ dp[j]max(dp[j],dp[j-v[i]]w[i]); } } coutdp[v1]; return 0; }01 背包一维必须倒序 j完全背包是正序 j。3、不考虑价值恰好装满的方案数内层循环j 从 V 倒序到 v[i]转移dp[j] (dp[j] dp[j‑v[i]]) % MOD①恰好装满 V答案dp[V]②体积不超过 V答案sum(dp[0]~dp[V]) % MOD代码模板#includebits/stdc.h using namespace std; int dp[1003]; const int N1e97; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; dp[0]1; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv;jv1[i];j--){ dp[j](dp[j]dp[j-v1[i]])%N; } } coutdp[v]; return 0; }4、体积不超过 V求能拿到最大价值的方案数题意先选出总价值最大的选法统计一共有多少种这样的选法。 背包容量 V物品体积不超过 V不一定非要把背包装满。 需要两个数组dp[j]容量 j 的背包可以获得的最大价值cnt[j]容量 j达到最大价值f[j]的方案数量初始化cnt其他都是0只有cnt[0]1,因为背包容量为0是只有一种方案数就是什么都不装。代码模板#includebits/stdc.h using namespace std; int const N1e97; int dp[1003]; int cnt[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;iv;i){ cnt[i]1; } for(int i0;in;i){ for(int jv;jv1[i];j--){ if(dp[j]dp[j-v1[i]]w1[i]){ dp[j]dp[j-v1[i]]w1[i]; cnt[j]cnt[j-v1[i]]%N; } else if(dp[j]dp[j-v1[i]]w1[i]){ cnt[j](cnt[j]cnt[j-v1[i]])%N; } } } coutcnt[v]; return 0; }5、背包问题求具体方案二维 dp 从后往前递推然后正向循环回溯输出选择物品编号用来输出 01 背包选的物品。数组含义dp[i][j]只考虑第i ~ n号物品背包容量为j时可以得到的最大价值。注意i从n往下算代表从第i件到最后一件物品。v1[i],w1[i]第i件物品体积、价值DP 递推部分i 从 n 到 1for(int in;i1;i--){ for(int jv;j0;j--){ dp[i][j]dp[i1][j]; // 情况1不选第i件物品 if(jv1[i]) dp[i][j]max(dp[i1][j], dp[i1][j-v1[i]]w1[i]); } }dp[i][j] dp[i1][j]不选i号物品那么就依赖后面i1~n物品的结果。如果背包装得下i物品jv1[i] 对比两种选择不选 idp[i1][j]选 idp[i1][j‑v1[i]] w1[i]选完i之后剩下容量j‑v1[i]再看后面i1~n物品取两者 max 赋值给dp[i][j]边界dp[n1][j]没有物品可以选全部是 0全局数组自动初始 0。和普通二维背包对比 普通二维dp[i][j]代表前 i 件物品1~ii 从 1 到 n。 这份代码dp[i][j]代表i~n 后缀物品i 从 n 倒推到 1。✂回溯部分找出到底选了哪些物品int vvv; for(int i1;in;i){ if(vv0) break; if(vvv1[i] dp[i][vv]dp[i1][vv-v1[i]]w1[i]){ couti ; vv-v1[i]; } }逻辑从第 1 件物品开始依次判断这件物品有没有被选上。 条件dp[i][vv] dp[i1][vv‑v1[i]] w1[i]含义当前最优价值 【选 i 物品后的价值】说明最优解里面选了 i 号物品。如果成立输出物品编号i背包剩余容量减去该物品体积vv - v1[i]如果不成立说明最优解没有选i直接看下一个i1。代码模板#includebits/stdc.h using namespace std; const int N1005; int v1[N],w1[N]; int dp[N][N]; int main(){ int n,v; cinnv; for(int i1;in;i){ cinv1[i]w1[i]; } for(int in;i1;i--){ for(int jv;j0;j--){ dp[i][j]dp[i1][j]; if(jv1[i]) dp[i][j]max(dp[i1][j],dp[i1][j-v1[i]]w1[i]); } } int vvv; for(int i1;in;i){ if(vv0) break; if(vvv1[i]dp[i][vv]dp[i1][vv-v1[i]]w1[i]){ couti ; vv-v1[i]; } } return 0; }6、二维费用的背包问题每件物品有两种消耗双重约束本题消耗 1体积 (v1[i])背包体积上限 v消耗 2重量 (m1[i])背包重量上限 m物品价值 (w1[i])每件物品最多选 1 次 求在体积≤v 并且 重量≤m条件下的最大价值。普通 01 背包只有 1 个约束体积二维费用背包增加第二个约束条件dp 数组多一维。dp 状态定义dp[j][k]总体积用了j总重量用了k可以获得的最大价值。状态转移dp[j][k]max(dp[j][k],dp[j‑v1[i]][k‑m1[i]]w1[i]);不选该物品保留原来dp[j][k]选该物品体积减去(v1[i])重量减去(m1[i])再加上当前物品价值。循环关键点for(int i0;in;i) for(int jv;jv1[i];j--) //体积维度倒序 for(int km;km1[i];k--) //重量维度也要倒序✅两个费用维度都必须倒序遍历一维 01 背包只需要容量倒序避免重复选同一个物品。二维费用 01 背包两维全部倒序。 只要有一维写成正序就会变成完全背包逻辑同一个物品可以多次选取直接 WA。j 循环和 k 循环可以互换先后顺序结果不变。初始化两种模式不要求装满本题代码全局 dp 数组默认 0允许体积、重量不用耗尽求最大价值。输出dp[v][m]。要求恰好装满dp 全部初始为负无穷dp[0][0]0。代表体积 0 重量 0 时价值为 0其余状态不可达。代码模板#includebits/stdc.h using namespace std; const int N1005; int dp[N][N]; int v1[N],m1[N],w1[N]; int main(){ int n,v,m; cinnvm; for(int i0;in;i){ cinv1[i]m1[i]w1[i]; } for(int i0;in;i){ for(int jv;jv1[i];j--){ for(int km;km1[i];k--){ dp[j][k]max(dp[j][k],dp[j-v1[i]][k-m1[i]]w1[i]); } } } coutdp[v][m]; return 0; }二、完全背包特点物品可以无限选取每件物品能选多次状态定义dp[j] 表示背包容量为 j 时能获得的最大价值1、一维DP转移方程d p [ j ] m a x ( d p [ j ] , d p [ j − v [ i ] ] w [ i ] ) dp[j]max(dp[j],dp[j-v[i]]w[i])dp[j]max(dp[j],dp[j−v[i]]w[i])代码模板#includebits/stdc.h using namespace std; int dp[1009]; int v1[1009],w1[1009]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv1[i];jv;j){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); } } coutdp[v]; return 0; }01 背包j 逆序jm; jv[i]防止重复选完全背包j 正序jv[i]; jm允许重复选取2、不考虑价值恰好装满的方案数内层循环j 从 v[i]正序到V转移dp[j] (dp[j] dp[j‑v[i]]) % MOD①恰好装满 V答案dp[V]②体积不超过 V答案sum(dp[0]~dp[V])%MOD代码模板#includebits/stdc.h using namespace std; int dp[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; dp[0]1; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv1[i];jv;j){ dp[j]dp[j-v1[i]]; } } coutdp[v]; return 0; }3、体积不超过 V求能拿到最大价值的方案数dp[j]背包容量j可以得到的最大价值全局数组默认初始为 0cnt[j]背包容量j取得dp[j]最大价值的方案数量初始化cnt[0]1;cnt[0]1背包体积为 0什么物品都不选价值 0算作 1 种合法方案。cnt[1...v]全局默认 0不需要赋值。循环for(int i0;in;i) for(int jv1[i];jv;j)j 从小到大正序完全背包允许同一物品重复选取。如果改成 01 背包内层改为for(int jv;jv1[i];j--)倒序转移代码完全不变。状态转移int choose dp[j-v1[i]] w1[i]; //选当前物品的总价值 if(dp[j] choose){ //选物品价值更大更新价值方案继承j‑v1[i]的方案 dp[j]choose; cnt[j]cnt[j-v1[i]]%N; }else if(dp[j]choose){ //选、不选价值相等两类方案相加 cnt[j](cnt[j]cnt[j-v1[i]])%N; } //choose dp[j]不选该物品dp、cnt保持原样代码模板#includebits/stdc.h using namespace std; int const N1e97; int dp[1003]; int cnt[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } cnt[0]1; for(int i0;in;i){ for(int jv1[i];jv;j){ if(dp[j]dp[j-v1[i]]w1[i]){ dp[j]dp[j-v1[i]]w1[i]; cnt[j]cnt[j-v1[i]]%N; } else if(dp[j]dp[j-v1[i]]w1[i]){ cnt[j](cnt[j]cnt[j-v1[i]])%N; } } } coutcnt[v]; return 0; }三、分组背包一维DP物品分成 n 组每组最多只能选 1 件物品组内物品互斥求背包容量 v 下最大总价值。数组含义s[i]第i组有多少件物品v1[i][k],w1[i][k]第i组组内第k件物品的体积、价值dp[j]背包容量j可以获得的最大价值三层循环顺序分组背包固定顺序for(组 i : 0~n‑1) //第一层遍历组别 for(j v downto 0) //第二层容量倒序不能正序 for(组内物品k) //第三层遍历本组所有物品循环顺序绝对不能乱。每一层作用第一层 i枚举每一组一组一组处理每组最多挑一件。第二层 jj 从 v 倒序到 0* 和 01 背包一样倒序防止同一组选多个物品。如果写成正序就会变成完全背包效果同一组可以重复拿多件直接 WA。第三层 k遍历本组里面每一个物品尝试本组选第 k 个物品更新 dp [j]。 转移式子dp[j]max(dp[j], dp[j‑v1[i][k]] w1[i][k]);dp[j‑v1[i][k]]是处理前面 i‑1 组得到的旧状态保证本组最多只选一件。代码模板#includebits/stdc.h using namespace std; int s[108]; int v1[108][108]; int w1[108][108]; int dp[108]; int main(){ int n,v; cinnv; for(int i0;in;i){ cins[i]; for(int j0;js[i];j){ cinv1[i][j]w1[i][j]; } } for(int i0;in;i){ for(int jv;j0;j--){ for(int k0;ks[i];k){ if(jv1[i][k]){ dp[j]max(dp[j],dp[j-v1[i][k]]w1[i][k]); } } } } coutdp[v]; return 0; }四、多重背包I、II朴素暴力版dp[j]背包容量为j时能拿到的最大价值。全局数组默认初始为 0。三层循环拆解for(int i0;in;i) //第一层枚举每一类物品 { int s,v1,w1; cinv1w1s; for(int jv;jv1;j--) //第二层容量j倒序模仿01背包 { //k枚举该物品选k件k∈[1,s] for(int k1;ksk*v1j;k) { dp[j]max(dp[j], dp[j‑k*v1] k*w1); } } }每一层作用第一层 i遍历每一类物品每一类最多拿s个。第二层 jj 从 v 往下倒序和 01 背包一样倒序保证使用上一轮 i‑1 的旧 dp 状态不会出现物品无限选。第三层 k暴力枚举选多少件k代表当前物品选k件。 条件ks不能超过该物品最多数量k*v1 j选 k 件的总体积不能超过当前背包容量 j状态转移方程dp[j] max(dp[j], dp[j - k*v1] k*w1);含义选k件该物品占用体积k*v1获得价值k*w1剩下容量j‑k*v1用前面物品的最优解。#includebits/stdc.h using namespace std; int dp[109]; int main(){ int n,v; cinnv; for(int i0;in;i){ int s,v1,w1; cinv1w1s; for(int jv;jv1;j--){ for(int k1;ksk*v1j;k){ dp[j]max(dp[j],dp[j-k*v1]k*w1); } } } coutdp[v]; return 0; }二进制优化版dp[j]容量j背包的最大价值全局数组默认初始 0。vv、vw存放二进制拆分之后生成的虚拟物品的体积、价值。把原来一类最多s件的物品拆成若干个新物品每个新物品代表一次性拿k件原物品。二进制拆分核心原理把数量s拆成若干个 2 的幂(1,2,4,8…)再加上剩下余数。 0~s 之间任意数目都可以用若干个拆分出的数字相加凑出来。举例s13k1取出 1s12k2k2取出 2s10k4k4取出 4s6k8k8 6退出循环把剩余 s6 加入 拆分结果1,2,4,6。1‑13任意数字都可以组合得到。每一组k件合并成一件虚拟物品虚拟体积 k ∗ v 1 k*v1k∗v1虚拟价值 k ∗ w 1 k*w1k∗w1第一段读入物品 二进制拆分for(int i0;in;i){ int v1,w1,s; cinv1w1s; int k1; while(ks){ vv.push_back(v1*k); vw.push_back(k*w1); ss-k; kk*2; } if(s0){ vv.push_back(v1*s); vw.push_back(s*w1); } }注意这里直接修改局部变量s不影响下一轮读入。第二段对所有虚拟物品跑 01 背包for(int i0;ivv.size();i){ for(int jv;jvv[i];j--){ dp[j]max(dp[j],dp[j-vv[i]]vw[i]); } }拆分完成后每一个虚拟物品只能选一次所以内层循环j倒序标准 01 背包写法。状态转移d p [ j ] m a x ( d p [ j ] , d p [ j − v v [ i ] ] v w [ i ] ) dp[j]max(dp[j],dp[j-vv[i]]vw[i])dp[j]max(dp[j],dp[j−vv[i]]vw[i])#includebits/stdc.h using namespace std; int dp[2003]; vectorintvv; //拆分后虚拟物品的体积 vectorintvw; //拆分后虚拟物品的价值 int main(){ int n,v; cinnv; for(int i0;in;i){ int v1,w1,s; cinv1w1s; int k1; //二进制拆分1,2,4,8…… while(ks){ vv.push_back(v1*k); vw.push_back(k*w1); ss-k; kk*2; } //剩余不足2的幂次单独作为一组 if(s0){ vv.push_back(v1*s); vw.push_back(s*w1); } } //全部虚拟物品当作01背包处理j倒序 for(int i0;ivv.size();i){ for(int jv;jvv[i];j--){ dp[j]max(dp[j],dp[j-vv[i]]vw[i]); } } coutdp[v]; return 0; }五、混合背包一维DP混合背包问题同一个题目里面同时存在三种物品s[i] -101 背包物品最多选 1 次s[i] 0完全背包物品可以无限选s[i] 0多重背包物品最多选s[i]件使用二进制拆分优化转成 01 背包vv,wwvector存储二进制拆分之后生成的 “新虚拟物品” 的体积和价值分模块知识点s [i]-101 背包for(int jv;jv1[i];j--){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); }内层循环容量倒序保证每件物品只能选一次。s [i]0完全背包for(int jv1[i];jv;j){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); }内层循环容量正序允许物品多次选取。s [i]0多重背包二进制拆分优化核心思想把s件物品拆成若干组1,2,4,8…剩余数每组当成一件新的 01 物品。 任意0~s之间的数量都可以用这些组组合凑出来。vv.clear(); ww.clear(); int k1; while(ks[i]){ vv.push_back(k*v1[i]); //k件合并为1个虚拟物品 ww.push_back(k*w1[i]); s[i]s[i]-k; k2*k; } if(s[i]0){ //剩下不足2的幂次的部分单独作为一组 vv.push_back(s[i]*v1[i]); ww.push_back(s[i]*w1[i]); } //拆分完成全部当做01背包倒序遍历 for(int jj0;jjvv.size();jj){ for(int kkv;kkvv[jj];kk--){ dp[kk]max(dp[kk],dp[kk-vv[jj]]ww[jj]); } }举例s13拆分1,2,4,6124613。 1‑13 任意数字都可以由其中若干项相加得到。整体逻辑混合背包遍历每一件物品根据s[i]的标记走不同背包逻辑01 → j 倒序完全 → j 正序多重 → 二进制拆分转为多件 01 物品j 倒序关键点dp 数组是共用的三种物品依次处理状态不断滚动更新。
背包基础篇（01、完全、分组、多重、混合）
背包基础篇01、完全、分组、多重、混合问题链接2. 01背包问题 - AcWing题库11. 背包问题求方案数 - AcWing题库12. 背包问题求具体方案 - AcWing题库8. 二维费用的背包问题 - AcWing题库3. 完全背包问题 - AcWing题库9. 分组背包问题 - AcWing题库4. 多重背包问题 I - AcWing题库5. 多重背包问题 II - AcWing题库7. 混合背包问题 - AcWing题库一、01 背包01 背包每件物品只能选一次物品有重量v[i]价值w[i]背包总容量V求最大总价值。1、二维 DP状态定义dp[i][j]前i件物品背包容量为j时的最大价值。转移方程不选第i件d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j]dp[i][j]dp[i−1][j]不选第i件d p [ i ] [ j ] d p [ i − 1 ] [ j − v [ i ] ] w [ i ] dp[i][j]dp[i-1][j-v[i]]w[i]dp[i][j]dp[i−1][j−v[i]]w[i](需要背包容量j大于等于v[i],表示可以装下这个物品 )代码模板#includebits/stdc.h using namespace std; const int N1005; int v1[N],w1[N]; // v1[]重量w1[]价值 int dp[N][N]; // dp[i][j]前i个物品背包容量j的最大价值 int main(){ int n,v; cinnv; // 读入n件物品重量、价值 for(int i1;in;i){ cinv1[i]w1[i]; } // 遍历每件物品 for(int i1;in;i){ // j倒序也能跑但二维推荐正序 for(int jv;j0;j--){ dp[i][j]dp[i-1][j]; // 情况1不选第i件物品 if(v1[i]j) // 背包装得下才可以选 dp[i][j]max(dp[i-1][j],dp[i-1][j-v1[i]]w1[i]); // 取选/不选的最大值 } } coutdp[n][v]; // n件物品容量v的最大答案 return 0; }2、一维 DP二维压缩成一维j 必须倒序遍历防止物品被多次选取如果是正序遍历的话容量是从小的开始的会导致一个物品在放入之后随着容量的增大会被再次放入会变成完全背包问题。状态定义dp[j]容量j背包的最大价值。转移方程d p [ j ] m a x ( d p [ j ] , d p [ j − v [ i ] ] w [ i ] ) dp[j]max(dp[j],dp[j-v[i]]w[i])dp[j]max(dp[j],dp[j−v[i]]w[i])关键点j从总容量V到v[i]倒序代码模板#includebits/stdc.h using namespace std; int main(){ int n,v1; cinnv1; vectorintv(n1),w(n1); for(int i0;in;i){ cinv[i]w[i]; } vectorintdp(v11); for(int i0;in;i){ for(int jv1;jv[i];j--){ dp[j]max(dp[j],dp[j-v[i]]w[i]); } } coutdp[v1]; return 0; }01 背包一维必须倒序 j完全背包是正序 j。3、不考虑价值恰好装满的方案数内层循环j 从 V 倒序到 v[i]转移dp[j] (dp[j] dp[j‑v[i]]) % MOD①恰好装满 V答案dp[V]②体积不超过 V答案sum(dp[0]~dp[V]) % MOD代码模板#includebits/stdc.h using namespace std; int dp[1003]; const int N1e97; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; dp[0]1; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv;jv1[i];j--){ dp[j](dp[j]dp[j-v1[i]])%N; } } coutdp[v]; return 0; }4、体积不超过 V求能拿到最大价值的方案数题意先选出总价值最大的选法统计一共有多少种这样的选法。 背包容量 V物品体积不超过 V不一定非要把背包装满。 需要两个数组dp[j]容量 j 的背包可以获得的最大价值cnt[j]容量 j达到最大价值f[j]的方案数量初始化cnt其他都是0只有cnt[0]1,因为背包容量为0是只有一种方案数就是什么都不装。代码模板#includebits/stdc.h using namespace std; int const N1e97; int dp[1003]; int cnt[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;iv;i){ cnt[i]1; } for(int i0;in;i){ for(int jv;jv1[i];j--){ if(dp[j]dp[j-v1[i]]w1[i]){ dp[j]dp[j-v1[i]]w1[i]; cnt[j]cnt[j-v1[i]]%N; } else if(dp[j]dp[j-v1[i]]w1[i]){ cnt[j](cnt[j]cnt[j-v1[i]])%N; } } } coutcnt[v]; return 0; }5、背包问题求具体方案二维 dp 从后往前递推然后正向循环回溯输出选择物品编号用来输出 01 背包选的物品。数组含义dp[i][j]只考虑第i ~ n号物品背包容量为j时可以得到的最大价值。注意i从n往下算代表从第i件到最后一件物品。v1[i],w1[i]第i件物品体积、价值DP 递推部分i 从 n 到 1for(int in;i1;i--){ for(int jv;j0;j--){ dp[i][j]dp[i1][j]; // 情况1不选第i件物品 if(jv1[i]) dp[i][j]max(dp[i1][j], dp[i1][j-v1[i]]w1[i]); } }dp[i][j] dp[i1][j]不选i号物品那么就依赖后面i1~n物品的结果。如果背包装得下i物品jv1[i] 对比两种选择不选 idp[i1][j]选 idp[i1][j‑v1[i]] w1[i]选完i之后剩下容量j‑v1[i]再看后面i1~n物品取两者 max 赋值给dp[i][j]边界dp[n1][j]没有物品可以选全部是 0全局数组自动初始 0。和普通二维背包对比 普通二维dp[i][j]代表前 i 件物品1~ii 从 1 到 n。 这份代码dp[i][j]代表i~n 后缀物品i 从 n 倒推到 1。✂回溯部分找出到底选了哪些物品int vvv; for(int i1;in;i){ if(vv0) break; if(vvv1[i] dp[i][vv]dp[i1][vv-v1[i]]w1[i]){ couti ; vv-v1[i]; } }逻辑从第 1 件物品开始依次判断这件物品有没有被选上。 条件dp[i][vv] dp[i1][vv‑v1[i]] w1[i]含义当前最优价值 【选 i 物品后的价值】说明最优解里面选了 i 号物品。如果成立输出物品编号i背包剩余容量减去该物品体积vv - v1[i]如果不成立说明最优解没有选i直接看下一个i1。代码模板#includebits/stdc.h using namespace std; const int N1005; int v1[N],w1[N]; int dp[N][N]; int main(){ int n,v; cinnv; for(int i1;in;i){ cinv1[i]w1[i]; } for(int in;i1;i--){ for(int jv;j0;j--){ dp[i][j]dp[i1][j]; if(jv1[i]) dp[i][j]max(dp[i1][j],dp[i1][j-v1[i]]w1[i]); } } int vvv; for(int i1;in;i){ if(vv0) break; if(vvv1[i]dp[i][vv]dp[i1][vv-v1[i]]w1[i]){ couti ; vv-v1[i]; } } return 0; }6、二维费用的背包问题每件物品有两种消耗双重约束本题消耗 1体积 (v1[i])背包体积上限 v消耗 2重量 (m1[i])背包重量上限 m物品价值 (w1[i])每件物品最多选 1 次 求在体积≤v 并且 重量≤m条件下的最大价值。普通 01 背包只有 1 个约束体积二维费用背包增加第二个约束条件dp 数组多一维。dp 状态定义dp[j][k]总体积用了j总重量用了k可以获得的最大价值。状态转移dp[j][k]max(dp[j][k],dp[j‑v1[i]][k‑m1[i]]w1[i]);不选该物品保留原来dp[j][k]选该物品体积减去(v1[i])重量减去(m1[i])再加上当前物品价值。循环关键点for(int i0;in;i) for(int jv;jv1[i];j--) //体积维度倒序 for(int km;km1[i];k--) //重量维度也要倒序✅两个费用维度都必须倒序遍历一维 01 背包只需要容量倒序避免重复选同一个物品。二维费用 01 背包两维全部倒序。 只要有一维写成正序就会变成完全背包逻辑同一个物品可以多次选取直接 WA。j 循环和 k 循环可以互换先后顺序结果不变。初始化两种模式不要求装满本题代码全局 dp 数组默认 0允许体积、重量不用耗尽求最大价值。输出dp[v][m]。要求恰好装满dp 全部初始为负无穷dp[0][0]0。代表体积 0 重量 0 时价值为 0其余状态不可达。代码模板#includebits/stdc.h using namespace std; const int N1005; int dp[N][N]; int v1[N],m1[N],w1[N]; int main(){ int n,v,m; cinnvm; for(int i0;in;i){ cinv1[i]m1[i]w1[i]; } for(int i0;in;i){ for(int jv;jv1[i];j--){ for(int km;km1[i];k--){ dp[j][k]max(dp[j][k],dp[j-v1[i]][k-m1[i]]w1[i]); } } } coutdp[v][m]; return 0; }二、完全背包特点物品可以无限选取每件物品能选多次状态定义dp[j] 表示背包容量为 j 时能获得的最大价值1、一维DP转移方程d p [ j ] m a x ( d p [ j ] , d p [ j − v [ i ] ] w [ i ] ) dp[j]max(dp[j],dp[j-v[i]]w[i])dp[j]max(dp[j],dp[j−v[i]]w[i])代码模板#includebits/stdc.h using namespace std; int dp[1009]; int v1[1009],w1[1009]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv1[i];jv;j){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); } } coutdp[v]; return 0; }01 背包j 逆序jm; jv[i]防止重复选完全背包j 正序jv[i]; jm允许重复选取2、不考虑价值恰好装满的方案数内层循环j 从 v[i]正序到V转移dp[j] (dp[j] dp[j‑v[i]]) % MOD①恰好装满 V答案dp[V]②体积不超过 V答案sum(dp[0]~dp[V])%MOD代码模板#includebits/stdc.h using namespace std; int dp[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; dp[0]1; for(int i0;in;i){ cinv1[i]w1[i]; } for(int i0;in;i){ for(int jv1[i];jv;j){ dp[j]dp[j-v1[i]]; } } coutdp[v]; return 0; }3、体积不超过 V求能拿到最大价值的方案数dp[j]背包容量j可以得到的最大价值全局数组默认初始为 0cnt[j]背包容量j取得dp[j]最大价值的方案数量初始化cnt[0]1;cnt[0]1背包体积为 0什么物品都不选价值 0算作 1 种合法方案。cnt[1...v]全局默认 0不需要赋值。循环for(int i0;in;i) for(int jv1[i];jv;j)j 从小到大正序完全背包允许同一物品重复选取。如果改成 01 背包内层改为for(int jv;jv1[i];j--)倒序转移代码完全不变。状态转移int choose dp[j-v1[i]] w1[i]; //选当前物品的总价值 if(dp[j] choose){ //选物品价值更大更新价值方案继承j‑v1[i]的方案 dp[j]choose; cnt[j]cnt[j-v1[i]]%N; }else if(dp[j]choose){ //选、不选价值相等两类方案相加 cnt[j](cnt[j]cnt[j-v1[i]])%N; } //choose dp[j]不选该物品dp、cnt保持原样代码模板#includebits/stdc.h using namespace std; int const N1e97; int dp[1003]; int cnt[1003]; int v1[1003],w1[1003]; int main(){ int n,v; cinnv; for(int i0;in;i){ cinv1[i]w1[i]; } cnt[0]1; for(int i0;in;i){ for(int jv1[i];jv;j){ if(dp[j]dp[j-v1[i]]w1[i]){ dp[j]dp[j-v1[i]]w1[i]; cnt[j]cnt[j-v1[i]]%N; } else if(dp[j]dp[j-v1[i]]w1[i]){ cnt[j](cnt[j]cnt[j-v1[i]])%N; } } } coutcnt[v]; return 0; }三、分组背包一维DP物品分成 n 组每组最多只能选 1 件物品组内物品互斥求背包容量 v 下最大总价值。数组含义s[i]第i组有多少件物品v1[i][k],w1[i][k]第i组组内第k件物品的体积、价值dp[j]背包容量j可以获得的最大价值三层循环顺序分组背包固定顺序for(组 i : 0~n‑1) //第一层遍历组别 for(j v downto 0) //第二层容量倒序不能正序 for(组内物品k) //第三层遍历本组所有物品循环顺序绝对不能乱。每一层作用第一层 i枚举每一组一组一组处理每组最多挑一件。第二层 jj 从 v 倒序到 0* 和 01 背包一样倒序防止同一组选多个物品。如果写成正序就会变成完全背包效果同一组可以重复拿多件直接 WA。第三层 k遍历本组里面每一个物品尝试本组选第 k 个物品更新 dp [j]。 转移式子dp[j]max(dp[j], dp[j‑v1[i][k]] w1[i][k]);dp[j‑v1[i][k]]是处理前面 i‑1 组得到的旧状态保证本组最多只选一件。代码模板#includebits/stdc.h using namespace std; int s[108]; int v1[108][108]; int w1[108][108]; int dp[108]; int main(){ int n,v; cinnv; for(int i0;in;i){ cins[i]; for(int j0;js[i];j){ cinv1[i][j]w1[i][j]; } } for(int i0;in;i){ for(int jv;j0;j--){ for(int k0;ks[i];k){ if(jv1[i][k]){ dp[j]max(dp[j],dp[j-v1[i][k]]w1[i][k]); } } } } coutdp[v]; return 0; }四、多重背包I、II朴素暴力版dp[j]背包容量为j时能拿到的最大价值。全局数组默认初始为 0。三层循环拆解for(int i0;in;i) //第一层枚举每一类物品 { int s,v1,w1; cinv1w1s; for(int jv;jv1;j--) //第二层容量j倒序模仿01背包 { //k枚举该物品选k件k∈[1,s] for(int k1;ksk*v1j;k) { dp[j]max(dp[j], dp[j‑k*v1] k*w1); } } }每一层作用第一层 i遍历每一类物品每一类最多拿s个。第二层 jj 从 v 往下倒序和 01 背包一样倒序保证使用上一轮 i‑1 的旧 dp 状态不会出现物品无限选。第三层 k暴力枚举选多少件k代表当前物品选k件。 条件ks不能超过该物品最多数量k*v1 j选 k 件的总体积不能超过当前背包容量 j状态转移方程dp[j] max(dp[j], dp[j - k*v1] k*w1);含义选k件该物品占用体积k*v1获得价值k*w1剩下容量j‑k*v1用前面物品的最优解。#includebits/stdc.h using namespace std; int dp[109]; int main(){ int n,v; cinnv; for(int i0;in;i){ int s,v1,w1; cinv1w1s; for(int jv;jv1;j--){ for(int k1;ksk*v1j;k){ dp[j]max(dp[j],dp[j-k*v1]k*w1); } } } coutdp[v]; return 0; }二进制优化版dp[j]容量j背包的最大价值全局数组默认初始 0。vv、vw存放二进制拆分之后生成的虚拟物品的体积、价值。把原来一类最多s件的物品拆成若干个新物品每个新物品代表一次性拿k件原物品。二进制拆分核心原理把数量s拆成若干个 2 的幂(1,2,4,8…)再加上剩下余数。 0~s 之间任意数目都可以用若干个拆分出的数字相加凑出来。举例s13k1取出 1s12k2k2取出 2s10k4k4取出 4s6k8k8 6退出循环把剩余 s6 加入 拆分结果1,2,4,6。1‑13任意数字都可以组合得到。每一组k件合并成一件虚拟物品虚拟体积 k ∗ v 1 k*v1k∗v1虚拟价值 k ∗ w 1 k*w1k∗w1第一段读入物品 二进制拆分for(int i0;in;i){ int v1,w1,s; cinv1w1s; int k1; while(ks){ vv.push_back(v1*k); vw.push_back(k*w1); ss-k; kk*2; } if(s0){ vv.push_back(v1*s); vw.push_back(s*w1); } }注意这里直接修改局部变量s不影响下一轮读入。第二段对所有虚拟物品跑 01 背包for(int i0;ivv.size();i){ for(int jv;jvv[i];j--){ dp[j]max(dp[j],dp[j-vv[i]]vw[i]); } }拆分完成后每一个虚拟物品只能选一次所以内层循环j倒序标准 01 背包写法。状态转移d p [ j ] m a x ( d p [ j ] , d p [ j − v v [ i ] ] v w [ i ] ) dp[j]max(dp[j],dp[j-vv[i]]vw[i])dp[j]max(dp[j],dp[j−vv[i]]vw[i])#includebits/stdc.h using namespace std; int dp[2003]; vectorintvv; //拆分后虚拟物品的体积 vectorintvw; //拆分后虚拟物品的价值 int main(){ int n,v; cinnv; for(int i0;in;i){ int v1,w1,s; cinv1w1s; int k1; //二进制拆分1,2,4,8…… while(ks){ vv.push_back(v1*k); vw.push_back(k*w1); ss-k; kk*2; } //剩余不足2的幂次单独作为一组 if(s0){ vv.push_back(v1*s); vw.push_back(s*w1); } } //全部虚拟物品当作01背包处理j倒序 for(int i0;ivv.size();i){ for(int jv;jvv[i];j--){ dp[j]max(dp[j],dp[j-vv[i]]vw[i]); } } coutdp[v]; return 0; }五、混合背包一维DP混合背包问题同一个题目里面同时存在三种物品s[i] -101 背包物品最多选 1 次s[i] 0完全背包物品可以无限选s[i] 0多重背包物品最多选s[i]件使用二进制拆分优化转成 01 背包vv,wwvector存储二进制拆分之后生成的 “新虚拟物品” 的体积和价值分模块知识点s [i]-101 背包for(int jv;jv1[i];j--){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); }内层循环容量倒序保证每件物品只能选一次。s [i]0完全背包for(int jv1[i];jv;j){ dp[j]max(dp[j],dp[j-v1[i]]w1[i]); }内层循环容量正序允许物品多次选取。s [i]0多重背包二进制拆分优化核心思想把s件物品拆成若干组1,2,4,8…剩余数每组当成一件新的 01 物品。 任意0~s之间的数量都可以用这些组组合凑出来。vv.clear(); ww.clear(); int k1; while(ks[i]){ vv.push_back(k*v1[i]); //k件合并为1个虚拟物品 ww.push_back(k*w1[i]); s[i]s[i]-k; k2*k; } if(s[i]0){ //剩下不足2的幂次的部分单独作为一组 vv.push_back(s[i]*v1[i]); ww.push_back(s[i]*w1[i]); } //拆分完成全部当做01背包倒序遍历 for(int jj0;jjvv.size();jj){ for(int kkv;kkvv[jj];kk--){ dp[kk]max(dp[kk],dp[kk-vv[jj]]ww[jj]); } }举例s13拆分1,2,4,6124613。 1‑13 任意数字都可以由其中若干项相加得到。整体逻辑混合背包遍历每一件物品根据s[i]的标记走不同背包逻辑01 → j 倒序完全 → j 正序多重 → 二进制拆分转为多件 01 物品j 倒序关键点dp 数组是共用的三种物品依次处理状态不断滚动更新。