背包简单模板经过缓慢的学习也是终于把背包九讲搞定而今特来补全博客01背包题目来源01背包问题题意有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。思路1.定义dp[i][j]i是考虑前i个物品j是当前容量整体含义就是我只考虑前i个物品背包容量是j时的最大价值。2.状态转移方程这道题可以通过画图进行更深的理解但我更喜欢直接通过状态转移方程理解所以我就主要说怎么去理解。其实这个01背包的状态转移方程还是十分好理解的但是因为我们接下来要进行一维的转换所以我就说下对于当前状态dp[i][j]来说我们要进行计算那我们就一定有俩种情况选和不选。补选的情况一定是上一物品也就是dp[i-1][j]这个状态下的值因为dp[i-1][j]的状态已经确定好了就是当前状态的最大我们不需要考虑它的选与不选所以回到我们当前第i个物品如果不选的话就是dp[i][j] dp[i-1][j]。如果我们要选的话我们就需要dp[i-1][j-v[i]] w[i]其中j-v[i]的意思是我们用了v[i]的容量选择了当前的物品其实还挺好理解的是吧然后因为我们本题的性质我们需要求的是最大价值所以判断选还是不选就是根据他们的比较谁最大就干啥。总的来说就是我们通过判断第i个物品选与不选来取得最大值不选dp[i - 1][j]选dp[i - 1][j - v[i]] w[i]从中取最大值dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])二维 code:#includebits/stdc.husingnamespacestd;constintN1005;intdp[N][N],v[N],w[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i];}for(inti1;in;i){for(intj0;jm;j){dp[i][j]dp[i-1][j];if(jv[i])dp[i][j]max(dp[i-1][j],dp[i-1][j-v[i]]w[i]);}}coutdp[n][m];return0;}优化 一维code通过二维的公式我们可以发现我们新的一层i总是与上一层i-1有关所以我们可以用一维进行优化这里涉及到一个滚动数组#includebits/stdc.husingnamespacestd;constintN1005;intdp[N],v[N],w[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i];}for(inti1;in;i){for(intjm;jv[i];j--){dp[j]max(dp[j],dp[j-v[i]]w[i]);}}coutdp[m];return0;}这里内层循环的逆序操作就是因为我们存的是实时更新的数所以我们每次更新只对能取当前物品i的进行更新如果正序会导致前边的数据改变使得后边的数据变得更大就比如dp[j] max(dp[j],dp[j - v[i]] w[i]);这里的dp[j]就发生了改变然后下一个k-v[i]jdp[k] max(dp[k],dp[j] w[i]);这样操作明显会变大其实这就是我们的完全背包遍历方式完全背包题目来源完全背包问题题意有 N 种物品和一个容量是 V 的背包每种物品都有无限件可用。第 i 种物品的体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输出最大价值。思路:1.定义dp[i][j]i是考虑前i个物品j是当前容量整体含义就是我只考虑前i个物品且无限选的数量与选法背包容量是j时的最大价值。2.状态转移方程;选0个dp[i-1][j]选1个dp[i-1][j - v[i]] w[i]选2个dp[i-1][j - 2*v[i]] 2*w[i]……选k个dp[i-1][j - k*v[i]] k*w[i]直到j - k*v[i] 0为止于是得到基础转移方程dp[i][j] max(dp[i-1][j - k*v[i]] k*w[i])其中k ≥ 0且k*v[i] ≤ j。但是这种方法写出来的暴力明显超时所以我们通过一些推导可以找到相应的关系进行转换dp[i][j]max(dp[i-1][j],// k 0dp[i-1][j-v]w,// k 1dp[i-1][j-2v]2w,// k 2...)dp[i][j-v]max(dp[i-1][j-v],// k 0dp[i-1][j-2v]w,// k 1dp[i-1][j-3v]2w,// k 2...)你会发现dp[i][j]的后面部分从k1开始正好等于dp[i][j - v] w。所以转移方程可以简化成dp[i][j] max(dp[i-1][j], dp[i][j - v[i]] w[i])它的实际含义是不选第i个物品dp[i-1][j]至少选一个第i个物品先选一个价值w[i]占v[i]剩下的容量j - v[i]仍然可以继续选第i个物品因为无限个所以是dp[i][j - v[i]] w[i]可以发现与01背包的区别在于用来取最大值的状态转移方程依靠的是当前层了**选物品时状态从dp[i-1][...]变成了dp[i][...]**就相当于可在同一行内进行重复选择二维code#includebits/stdc.husingnamespacestd;constintN1005;intdp[N][N],v[N],w[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i];}for(inti1;in;i){for(intj0;jm;j){dp[i][j]dp[i-1][j];if(jv[i]){dp[i][j]max(dp[i-1][j],dp[i][j-v[i]]w[i]);}}}coutdp[n][m];return0;}优化 一维code#includebits/stdc.husingnamespacestd;constintN1005;intdp[N],v[N],w[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i];}for(inti1;in;i){for(intjv[i];jm;j){dp[j]max(dp[j],dp[j-v[i]]w[i]);}}coutdp[m];return0;}发现没我们这里内层循环就采用了正序正是因为我们的同一物品的次数无限所以可以这样操作多重背包题目来源多重背包问题 I题意有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有s i s_isi​件每件体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。思路1.定义dp[i][j]i是考虑前i个物品j是当前容量整体含义就是我只考虑前i个物品且有限选的数量与选法背包容量是j时的最大价值。2.状态转移方程我们可以根据我们01背包的模板进行操作也就是把我们多重背包分成每个只能拿一个物品这样就变成01背包的操作了多加一层循环直接套用01背包的状态转移方程即可另一种方法类似于完全背包的推导过程选0个dp[i-1][j]选1个dp[i-1][j - v[i]] w[i]选2个dp[i-1][j - 2*v[i]] 2*w[i]……选k个dp[i-1][j - k*v[i]] k*w[i]直到j - k*v[i] 0 k s[i]为止所以我们的状态转移方程可以写成dp[i][j] max(dp[i][j], dp[i-1][j-k*v[i]]k*w[i])补充这个套路就是我们的完全背包推导过程但时间复杂度是3次方在稍大的数据下轻松超时所以我们完全背包不用这个状态转移方程二维code#includebits/stdc.husingnamespacestd;constintN105;intdp[N][N],v[N],w[N],s[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i]s[i];}for(inti1;in;i){for(intj0;jm;j){dp[i][j]dp[i-1][j];for(intk1;ks[i]k*v[i]j;k){dp[i][j]max(dp[i][j],dp[i-1][j-k*v[i]]k*w[i]);}}}coutdp[n][m];return0;}优化 一维code还是跟我们的01背包一样要进行逆序操作#includebits/stdc.husingnamespacestd;constintN105;intdp[N],v[N],w[N],s[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i]s[i];}for(inti1;in;i){for(intjm;jv[i];j--){// dp[j]dp[j];for(intk1;ks[i]k*v[i]j;k){dp[j]max(dp[j],dp[j-k*v[i]]k*w[i]);}}}coutdp[m];return0;}我再附上另一种这一种更好理解我们分解为01背包的操作#includebits/stdc.husingnamespacestd;constintN105;intdp[N],v[N],w[N],s[N];intmain(){intn,m;cinnm;for(inti1;in;i){cinv[i]w[i]s[i];}for(inti1;in;i){for(intk1;ks[i];k){for(intjm;jv[i];j--){dp[j]max(dp[j],dp[j-v[i]]w[i]);}}}coutdp[m];return0;}题目来源多重背包问题 II题意有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有s i s_isi​件每件体积是v i v_ivi​价值是w i w_iwi​。求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。输出最大价值。这里题目跟上一题一样但是一样的写法会超时所以我们要进行优化操作思路利用二进制数的性质把s[i]个物品拆成1, 2, 4, 8, ..., 剩余几个“打包组”每组当成一个01背包物品。比如s 13拆成1, 2, 4, 6因为 13 1 2 4 6。用这 4 个打包组可以组合出 0~13 中的任意数量。所以我们还是先拆分成好几个物品然后用01背包的操作进行接下来我就直接给一维code了code#includebits/stdc.husingnamespacestd;constintN2005;intdp[N];structGood{intv,w;};intmain(){intn,m;cinnm;vectorGoodgoods;for(inti1;in;i){intv1,w1,s1;cinv1w1s1;for(intk1;ks1;k*2){goods.push_back({v1*k,w1*k});s1-k;}if(s10)goods.push_back({v1*s1,w1*s1});}for(autox:goods){for(intjm;jx.v;j--){dp[j]max(dp[j],dp[j-x.v]x.w);}}coutdp[m];return0;}分组背包:题目来源分组背包问题题意有 N 组物品和一个容量是 V 的背包。每组物品有若干个同一组内的物品最多只能选一个。每件物品的体积是v i j v_{ij}vij​价值是w i j w_{ij}wij​其中 i 是组号j 是组内编号。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。思路1.定义dp[i][j]表示所有只考虑前i组物品且总体积不超过j的最大值。2.状态转移方程dp[j] max(dp[j], dp[j-v[k]]w[k]);k是当前组第k个物品还是跟我们的01背包相似只不过在这里我们需要多一层遍历细节看代码。简单来说我们就是通过这个操作加上滚动数组操作实时更新每个容量下选哪个物品的价值是最大的code#includebits/stdc.husingnamespacestd;constintN105;intdp[N],v[N],w[N];intmain(){intn,m;cinnm;for(inti1;in;i){ints;cins;for(intj1;js;j)cinv[j]w[j];for(intjm;j0;j--){for(intk1;ks;k){if(jv[k])dp[j]max(dp[j],dp[j-v[k]]w[k]);}}}coutdp[m];return0;}我们对容量j的遍历还是用逆序这样能保证用的是上一层的状态不会变成完全背包操作总结背包这个东西写出来的代码确实很奇妙但状态转移方程写出来一切都还是有迹可循的这期先写模版下期对剩余的题目进行进阶。