代码随想录算法训练营第四十四天| 背包问题、背包问题之滚动数组、416. 分割等和子集
背包问题
题目链接：背包问题
文档讲解：代码随想录/背包问题
视频讲解：视频讲解-背包问题
状态：已完成（1遍）
解题过程
这几天属实是有点分身乏术了，先直接看题解AC了，二刷的时候再来补上自己的思路和尝试吧。
看完代码随想录之后的想法
用动态规划五部曲：
- 确定dp数组以及下标的含义：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少；
- 确定递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
-
代码初始化如下：
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]; } - 确定遍历顺序：先遍历物品再遍历背包；
- 举例推导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遍）
解题过程
看完代码随想录之后的想法
用动态规划五部曲：
- 确定dp数组以及下标的含义：dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]；
- 确定递推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); -
代码初始化如下：假设物品价值都大于0，初始化时都为0就可以了
- 确定遍历顺序：
倒序遍历是为了保证物品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
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
- 举例推导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遍）
解题过程
看完代码随想录之后的想法
用动态规划五部曲：
- 确定dp数组以及下标的含义：dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]；
- 确定递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])；
- dp数组如何初始化：本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了;
- 确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
- 举例推导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;
};