《代码随想录》刷题打卡day30：动态规划-背包问题part01

【46.携带研究材料】方法一二维dp01背包思路确定dp数组及下标含义dp[i] [j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少。确定递推公式**dp[i] [j] max(dp[i-1] [j] , dp[i-1] [j-weight[i]] value[i]) **dp数组如何初始化初始化一定要根据dp数组的定义来进行dp[0] [j]初始化为0或者value[0]取决于j是否大于等于value[0]dp[i] [0]初始化为0其他下标初始为什么数值都可以因为都会被覆盖。遍历顺序先遍历物品还是先遍历背包重量都可以先遍历物品比较好理解// weight数组的大小 就是物品个数for(inti1;iweight.size();i){// 遍历物品for(intj0;jbagweight;j){// 遍历背包容量if(jweight[i])dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);}}举例推导dp数组进行验证代码解答// 二维dp数组解法#includebits/stdc.husingnamespacestd;intmain(){intn,bagweight;cinnbagweight;vectorintweight(n,0);vectorintvalue(n,0);for(inti0;in;i)cinweight[i];for(inti0;in;i)cinvalue[i];vectorvectorintdp(weight.size(),vectorint(bagweight1,0));for(intiweight[0];ibagweight;i){dp[0][i]value[0];}for(inti1;iweight.size();i){// 遍历物品for(intj0;jbagweight;j){// 遍历背包容量if(jweight[i])dp[i][j]dp[i-1][j];//如果装不下这个物品,那么就继承dp[i - 1][j]的值else{dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i]]value[i]);}}}coutdp[n-1][bagweight]endl;return0;}方法二一维dp01背包思路对于背包问题其实状态都是可以压缩的。在使用二维数组的时候递推公式dp[i] [j] max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] value[i]);其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i] [j] max(dp[i] [j], dp[i] [j - weight[i]] value[i]);与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。这就是滚动数组的由来需要满足的条件是上一层可以重复利用直接拷贝到当前层。dp[i] [j]里的i和j表达的是什么了i是物品j是背包容量。dp[i] [j] 表示从下标为[0~i]的物品里任意取放进容量为j的背包价值总和最大是多少。确定dp数组及下标含义在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。。确定递推公式二维dp公式**dp[i] [j] max(dp[i-1] [j] , dp[i-1] [j-weight[i]] value[i]) **一维dp公式dp[j] max(dp[j] , dp[j-weight[i]] value[i])把i的维度去掉只保留j维度dp数组如何初始化关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。那么dp数组除了下标0的位置初始为0其他下标应该初始化多少呢看一下递归公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。那么我假设物品价值都是大于0的所以dp数组初始化的时候都初始为0就可以了。遍历顺序只能先遍历物品for(inti0;iweight.size();i){// 遍历物品for(intjbagWeight;jweight[i];j--){// 遍历背包容量dp[j]max(dp[j],dp[j-weight[i]]value[i]);}}和二维dp的写法中遍历背包的顺序是不一样的二维dp遍历的时候背包容量是从小到大而一维dp遍历的时候背包是从大到小。为什么呢**倒序遍历是为了保证物品i只被放入一次**但如果一旦正序遍历了那么物品0就会被重复加入多次举一个例子物品0的重量weight[0] 1价值value[0] 15如果正序遍历dp[1] dp[1 - weight[0]] value[0] 15dp[2] dp[2 - weight[0]] value[0] 30此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。为什么倒序遍历就可以保证物品只放入一次呢倒序就是先算dp[2]dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0dp[1] dp[1 - weight[0]] value[0] 15所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。那么问题又来了为什么二维dp数组遍历的时候不用倒序呢因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1] [j]计算而来本层的dp[i] [j]并不会被覆盖动手试一试空想不靠谱实践出真知再来看看两个嵌套for循环的顺序代码中是先遍历物品嵌套遍历背包容量那可不可以先遍历背包容量嵌套遍历物品呢不可以因为一维dp的写法背包容量一定是要倒序遍历原因上面已经讲了如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品即背包里只放入了一个物品。**所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的**这一点一定要注意。举例推导dp数组进行验证代码解答// 一维dp数组实现#includeiostream#includevectorusingnamespacestd;intmain(){// 读取 M 和 NintM,N;cinMN;vectorintcosts(M);vectorintvalues(M);for(inti0;iM;i){cincosts[i];}for(intj0;jM;j){cinvalues[j];}// 创建一个动态规划数组dp初始值为0vectorintdp(N1,0);// 外层循环遍历每个类型的研究材料for(inti0;iM;i){// 内层循环从 N 空间逐渐减少到当前研究材料所占空间for(intjN;jcosts[i];--j){// 考虑当前研究材料选择和不选择的情况选择最大值dp[j]max(dp[j],dp[j-costs[i]]values[i]);}}// 输出dp[N]即在给定 N 行李空间可以携带的研究材料最大价值coutdp[N]endl;return0;}【416.分割等和子集】有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。背包问题有多种背包方式常见的有01背包、完全背包、多重背包、分组背包和混合背包等等。要注意题目描述中商品是不是可以重复放入。即一个商品如果可以重复多次放入是完全背包而只能放入一次是01背包写法还是不一样的。思路元素我们只能用一次如果使用背包那么也是01背包首先本题要求集合里能否出现总和为 sum / 2 的子集。既有一个 只能装重量为 sum / 2 的背包商品为数字这些数字能不能把 这个背包装满。那每一件商品是数字的话对应的重量和价值是多少呢一个数字只有一个维度即重量等于价值。当数字可以装满承载重量为 sum / 2 的背包的背包时这个背包的价值也是 sum / 2。那么这道题就是装满承载重量为 sum / 2 的背包价值最大是多少如果最大价值是 sum / 2说明正好被商品装满了。因为商品是数字重量和对应的价值是相同的。classSolution{public:boolcanPartition(vectorintnums){intsum0;vectorintdp(10001,0);// dp[i]表示背包容量为i的时候能装的物品的最大价值当 dp[sum/2]sum/2 时满足题意// 题目中说每个数组中的元素不会超过 100数组的大小不会超过 200// 总和不会大于20000背包最大只需要其中一半所以10001大小就可以了for(inti0;inums.size();i){sumnums[i];}if(sum%21)returnfalse;inttargetsum/2;for(inti0;inums.size();i){for(intjtarget;jnums[i];j--){// 每一个元素一定是不可重复放入所以从大到小遍历dp[j]max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[target]target)returntrue;elsereturnfalse;}};补充1、物品价值全正数本题分割等和子集初始化整个 dp 数组统一赋值 0理由没放物品时所有背包都是空的价值为 0正数物品只会让价值变大max运算可以正常更新合法最大值不会出现虚假可行解最后直接比对数值即可。2、价值包含负数初始化dp [0]0其余下标初始为负无穷理由负无穷代表初始除了容量 0 之外其余容量都凑不出来若依旧初始化为 0会误把空载的 0 当成有效方案负数价值计算结果出错最终数值不等于负无穷才代表存在可行拼凑方案。