打卡第34天------动态规划-01背包
我目前刷leetcode上的题的时候，不仅每天按照代码随想录的算法训练营的进度来刷题，也会自己开始在leetcode上刷题了，有些简单的题目，不用看题解就能做出来了，这也是一种进步呀。希望可以尽快找到下家工作单位，分秒必争，不浪费自己的一分一毫时间，与时间赛跑的过程呀。
一、0-1背包问题理论基础
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
1、二维数组
先遍历物品i，再遍历背包j
- 确定dp数组含义：dp[i][j]，表示从下标为[0~i]的物品里任意取，放进容量为j的背包，价值总和的最大值。
- 确定递推公式：dp[i][j] = Math.max( dp[i-1][j], dp[i-1][j - weight[i]]+value[i] )；
- dp数组初始化
- 打印dp数组
2、一维数组
这里跟二维数组不同的是，在遍历背包的时候是倒着遍历，从大到小，这样子倒序遍历是为了保证物品i只能被放入一次。
- 确定dp数组含义：dp[j]，表示容量为j的背包，所背的物品价值最大为dp[j]；
- 确定递推公式：dp[j] = Math.max( dp[j], dp[j - weight[i]] + value[i] )
- dp数组初始化：
- 打印dp数组
因为一维数组更加直观、简洁，而且空间负责度还降了一个数据量级。所以在解决01背包的问题，基本上都是采用一维数组来解决的。
二、分割等和子集
leetcode题目链接：416. 分割等和子集
题目描述：
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
具体看一下思路和解题代码：
/*** @param {number[]} nums* @return {boolean}*/
// 既是重量又是价值
// dp[j] 背包容量为j。最大值为dp[j]
// 判断背包装满了，dp[target] == target, target = sum / 2;
// 二维数组压缩过来的。状态压缩，数组降维。
// 递推公式：dp[j] = Math.max(dp[j], dp[j - weight[i] + value[i]])
// 对于本题的递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i] + nums[i]])
// 初始化：dp[0] = 0；
var canPartition = function(nums) {const sum = nums.reduce((pre, curr) => pre + curr, 0);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;
};