代码随想录算法训练营第四十四天| 背包问题、背包问题之滚动数组、416. 分割等和子集

背包问题

题目链接：背包问题

文档讲解：代码随想录/背包问题

视频讲解：视频讲解-背包问题

状态：已完成（1遍）

解题过程 

这几天属实是有点分身乏术了，先直接看题解AC了，二刷的时候再来补上自己的思路和尝试吧。

看完代码随想录之后的想法 

用动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少；
2. 确定递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 代码初始化如下：

   for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。dp[0][j] = 0;
   }
   // 正序遍历
   for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
   }

4. 确定遍历顺序：先遍历物品再遍历背包；
5. 举例推导dp数组：

讲解代码如下：

function testWeightBagProblem (weight, value, size) {// 定义 dp 数组const len = weight.length,dp = Array(len).fill().map(() => Array(size + 1).fill(0));// 初始化for(let j = weight[0]; j <= size; j++) {dp[0][j] = value[0];}// weight 数组的长度len 就是物品个数for(let i = 1; i < len; i++) { // 遍历物品for(let j = 0; j <= size; j++) { // 遍历背包容量if(j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}console.table(dp)return dp[len - 1][size];
}function test () {console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}test();

---

 背包问题之滚动数组

题目链接：背包问题之滚动数组

文档讲解：代码随想录/背包问题之滚动数组

视频讲解：视频讲解-背包问题之滚动数组

状态：已完成（1遍）

解题过程  

 看完代码随想录之后的想法 

用动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]；
2. 确定递推公式：

   dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 代码初始化如下：假设物品价值都大于0，初始化时都为0就可以了

4. 确定遍历顺序：

   倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

   举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15

   如果正序遍历

   dp[1] = dp[1 - weight[0]] + value[0] = 15

   dp[2] = dp[2 - weight[0]] + value[0] = 30

   此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。

   为什么倒序遍历，就可以保证物品只放入一次呢？

   倒序就是先算dp[2]

   dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

   dp[1] = dp[1 - weight[0]] + value[0] = 15

   所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

5. 举例推导dp数组

讲解代码如下：

function testWeightBagProblem(wight, value, size) {const len = wight.length, dp = Array(size + 1).fill(0);for(let i = 1; i <= len; i++) {for(let j = size; j >= wight[i - 1]; j--) {dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]);}}return dp[size];
}function test () {console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
}test();

---

416. 分割等和子集

题目链接：416. 分割等和子集

文档讲解：代码随想录/分割等和子集

视频讲解：视频讲解-分割等和子集

状态：已完成（1遍）

解题过程  

看完代码随想录之后的想法 

用动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]；
2. 确定递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；
3. dp数组如何初始化：本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了;
4. 确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
5. 举例推导dp数组：

   按照这个递推公式我们来推导一下，dp数组应该是如下的数列： 10 15 30  。

讲解代码如下：

var canPartition = function(nums) {const sum = (nums.reduce((p, v) => p + v));if (sum & 1) return false;const dp = Array(sum / 2 + 1).fill(0);for(let i = 0; i < nums.length; i++) {for(let j = sum / 2; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);if (dp[j] === sum / 2) {return true;}}}return dp[sum / 2] === sum / 2;
};