文章目录KEY1语法1 如何初始化二维数组2 数组求和用 accumulate(v.begin(), v.end(), 0);2学会把问题理解成01背包问题的形式然后用01背包的套路去解决01背包问题 二维整个代码01背包问题 一维整个代码416. 分割等和子集思路整个代码KEY1语法1 如何初始化二维数组intm3,n4;// 创建一个 3 行 4 列的二维 vector全部元素初始化为 0vectorvectorintdp(m,vectorint(n,0));// 如果想全部初始化为 -1 或其他值vectorvectorintdp(m,vectorint(n,-1));2 数组求和用accumulate(v.begin(), v.end(), 0);accumulate(v.begin(),v.end(),0);2学会把问题理解成01背包问题的形式然后用01背包的套路去解决01背包问题 二维别看卡尔的视频看算法课本上的说法即可两个都对但是数组大小定义不太一样别搞混了这是课本注意红框两个部分即可整个代码#includebits/stdc.husing namespace std;intmain(){intm,n;cinmn;vectorintw(m);vectorintv(m);for(inti0;im;i){cinw[i];}for(inti0;im;i){cinv[i];}vectorvectorintdp(m1,vectorint(n1,0));for(inti0;im1;i){dp[i][0]0;}for(inti0;in1;i){if(iw[0]){dp[0][i]0;}else{dp[0][i]0;}}for(inti1;im1;i){for(intj1;jn1;j){if(w[i-1]j)dp[i][j]dp[i-1][j];else{dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i-1]]v[i-1]);}}}coutdp[m][n];}01背包问题 一维核心把原来的二维数组换成只有一行的一维数组节省空间注意这一行是从后往前遍历因为下图整个代码#includebits/stdc.husing namespace std;intmain(){intm,n;cinmn;vectorintw(m);vectorintv(m);for(inti0;im;i){cinw[i];}for(inti0;im;i){cinv[i];}// vectorvectorint dp(m1,vectorint(n1,0));vectorintdp(n1,0);for(inti1;im1;i){for(intjn;j0;j--){if(w[i-1]j)dp[j]dp[j];else{dp[j]max(dp[j],dp[j-w[i-1]]v[i-1]);}}}coutdp[n];}416. 分割等和子集关键在于问题建模思路题意把数组划分成两个子集是左边这样而不是右边这样所以相当于找到这个数组的一个子集让其和等于数组之和的 1 / 2这样剩下的其他数之和也为数组之和的 1 / 2⇒ 相当于一个01背包问题需要找到合适的物品组合让其和为数组之和的 1 / 2注意与01背包相比背包问题中的weight[],value[]在这里都为nums[]注 但是这样做虽然通过了但是耗时多carl网用的是一维数组等方法。如果需要提速可去看我目前没看。整个代码class Solution{public:boolcanPartition(vectorintnums){intsizenums.size();intc;caccumulate(nums.begin(),nums.end(),0);if(c%21)returnfalse;else{cc/2;}vectorvectorintdp(size1,vectorint(c1,0));for(inti1;isize1;i){for(intj1;jc1;j){if(nums[i-1]j)dp[i][j]dp[i-1][j];else{dp[i][j]max(dp[i-1][j],dp[i-1][j-nums[i-1]]nums[i-1]);}}}if(dp[size][c]c)returntrue;returnfalse;}};第九章 动态规划part03正式开始背包问题背包问题还是挺难的虽然大家可能看了很多背包问题模板代码感觉挺简单但基本理解的都不够深入。如果是直接从来没听过背包问题可以先看文字讲解慢慢了解 这是干什么的。如果做过背包类问题可以先看视频很多内容是自己平时没有考虑到位的。背包问题力扣上没有原题大家先了解理论今天就安排一道具体题目。详细布置01背包问题 二维https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html视频讲解https://www.bilibili.com/video/BV1cg411g7Y601背包问题 一维https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html视频讲解https://www.bilibili.com/video/BV1BU4y177kY分割等和子集本题是 01背包的应用类题目https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html视频讲解https://www.bilibili.com/video/BV1rt4y1N7jE