Day 42
01. 背包问题 - 二维
<1> 01 背包问题
有 n 个物品和最多能装重量为 w 的背包，第 i 件物品的重量为 weight[i]，得到的价值是 value[i]，那如何将这些物品装入背包能获取最大的价值呢？
背包问题的一个很经典的 求最值 的问题，但因为其动态规划的过于的经典，很多朋友其实忽略了它的暴力解法，每一件物品只有两种状态：取或者不取，所以通过 回溯算法 将所有的情况遍历出来，可以求得最终的结果。
回溯算法示例：
java">public static void backtracking(int n) {
if (n == weight.length - 1 && m <= w) {
// 表明遍历到最终的物品
res = Math.max(res, v);
return;
}
for (int i = 0; i < 2; i++) {
if (i == 0) {
// 取的情况
v += value[n];
m += weight[n];
backtracking(n + 1);
v -= value[n];
m -= weight[n];
} else {
// 不取该物品的情况
backtracking(n + 1);
}
}
}
这样遍历完之后时间复杂度达到了 O(2n)。
<2> 动态规划优化
利用回溯算法解题的时间复杂度达到了 指数 级别，所以必须要考虑优化的方法。
因为本题的最优解收到 两个维度 的限制，一个是 背包的容量，一个是 选取的物品的重量（这个重量又被能选择哪些物品所影响），在这两个内容的限制下去求得最优的价值，所以在设计 dp 数组的时候也要同时将这两个因素考虑在内。
在设计 dp 数组的时候考虑的就是在 某个背包容量下，选取某些物品 能达到的最优价值总和；那 dp[i][j] 就是从下标为 0 到 i 的范围内任意取，放到容量为 j 的背包里，能收获的 最大价值 是多少。
这样就可以开始确定递推公式了：要紧扣两个限制条件，一个物品仅仅有两种情况：
- 不取这个物品，那此时价值最大的情况就是
dp[i - 1][j]，也就是在 这个容量下 取得的范围限制在0到i - 1。 - 取这个物品，但也要注意是在 这个容量下 去取的，也就是
dp[i - 1][j - weight[i]] + value[i]，时刻要记得另一个限制，也就是背包的容量。
最优解毫无疑问就是其中的最大值，也即：
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
现在看一个具体的例子来讨论 dp 数组的初始化：
物品的重量和价值：
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
背包的容量 4，最后形成一个三行五列的数组
初始化的关键是 dp[i] 等式右边的所有数据在遍历到 dp[i] 的时候一定是被填充过的。
比如遍历到 粉色 的节点，此时需要的是它的正上方和左上方的节点（为了保证数组下标不越界，此时的 j 必须要大于等于 weight[i] 否则这个物品就一定无法取得）。
所以要将所有没有上方或者左上方的节点全部初始化，因为依据上面的递推公式无法求出这些节点的值，也即这些节点：
dp[i][j] 就是从下标为 0 到 i 的范围内任意取，放到容量为 j 的背包里，能收获的 最大价值 是多少
那第一 列 毫无疑问被初始化成 0，第一行则为能取得物品 0 的时候价值为 value[0] 否则为 0，因为此时限制只能取得物品 0，比如上面那个例子，初始化之后的结果就是：
java">// 遍历第一行
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 0;
}
// 遍历第一列
for (int i = weight[0]; i < dp[0].length; i++) {
dp[i] = weight[0];
}
接下来确定遍历的顺序，因为我们的
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 也就是行表示选取的物品，列表示背包的容量，但其实这个递归公式也可以改写成：
dp[i][j] = Math.max(dp[i][j - 1], dp[i - weight[j]][j - 1] + value[j]) 行为背包的容量，列为选取的物品；这两个其实就对应着两种遍历顺序：先遍历物品还是先遍历背包？
其实两种都是可以的，这两种情况推出一个节点所需要的数据都在 左上角，不影响公式的推导，但因为大多数都是先遍历物品，而且在含义上也更易理解，所以平时建议写的时候先去遍历物品，对于先遍历背包的能够理解和写出代码即可。
那现在写出代码：
java">class Solution {
public int BagProblem(int[] weight, int[] value, int bagSize) {
int n = weight.length; // 物品的数量
int[][] dp = new int[n][bagSize + 1];
// 初始化 dp 数组
for (int i = weight[0]; i < dp[0].length; i++) {
dp[0][i] = value[0];
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (j >= weight[i]) {
// 可以放下物品的情况
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
} else {
// 不能放下物品的情况
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][bagSize];
}
}
02. 背包问题 - 一维
💡 相较于二维的方法，我认为一维的方法不止是在写法上，也是在性能上的一种优化。
可以观察一下上面的推导中的这一部分：
java">if (j >= weight[i]) {
// 可以放下物品的情况
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
} else {
// 不能放下物品的情况
dp[i][j] = dp[i - 1][j];
}
当出现 else 的情况，也就是背包容量装不下该物品的时候，这时候就是 直接将上一行的值原封不动的照搬下来，所以会去考虑：能否从 weight[i] 开始遍历呢？但是由于二维数组的限制，还需要将上面那一行的剩余部分通过遍历挪下来，还是上面那个例子：
那既然通过二维数组无法实现，那是不是可以考虑一维数组呢？
只要我不去修改那部分的值也就相当于直接挪下来了，试一下：
这时候只要解决 3 和 4 的问题其实就可以得到一个可行的方法了；回顾上面的推导公式，推导出一个节点的新值其实只需要它的 左上角的节点即可，那一维数组的这个左上角在哪呢？就在 本行 嘛，为了保证左上角一定有值，遍历就需要 从后向前去遍历，遍历的终点就是 j < weight[i]，这样其实就将二维数组的方法转成一维的了。
之所以一维数组能够解决问题，其本质还是递推公式的性质：推导一个节点只需要 左上角 的值。
看一下对比的关系因为上一行的内容相当于挪到本行的，所以不需要 i - 1，这就是新得到的递归公式。
写出代码
java">class Solution {
public int BagProblem(int[] weight, int[] value, int bagSize) {
int n = weight.length; // 物品的数量
int[] dp = new int[bagSize + 1];
// 初始化 dp 数组
for (int i = weight[0]; i < dp.length; i++) {
dp[i] = value[0];
}
for (int i = 1; i < n; i++) {
for (int j = dp.length - 1; j >= weight[i]; j--) {
// 可以放下物品的情况
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[bagSize];
}
}
💡 其实这个一位数组的遍历还隐藏着一个特性，如果从前向后遍历其实得到的是有 无限个 物品的情况
看一下这个递推公式
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);按照这个递推公式遍历一下物品 1 来感受一下
推导出来的部分是这样的，即物品有无限个的情况。
03. 分割等和子集（No. 416）
题目链接
代码随想录题解
<1> 题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
<2> 笔记
这道题是背包问题的一个经典的实例问题，其实一开始看到这个题的时候并没有想到往背包方向靠的思路，而是当成了组合问题去做，但是在写的时候突然想到，这不就是 找一个子集，使得它们的和等于原集合和的一半 嘛？
再继续深入的想一下，如何才能凑出这个原集合的和的一半值呢？为了好表述这里将这个值设为 target，只考虑子集的和 小于或者等于 target 的情况，这个问题就可以转化为：
从集合中的所有元素中选取元素，刨去大于 target 的那部分，它们的和的最大值能否达到 target？
是不是感觉和背包问题有点像了？这个 target 就是限制最大值的指标，集合中的元素的大小（选取范围）就是限制的另一个部分，这不正是背包问题的 两个限制条件 嘛？再继续类比，这个 target，其实就是 背包的容量，集合中的元素就是物品，其重量和价值 都是 nums[i]。
将其转换成背包问题去做，只需要判断最右下角的那个元素是否 等于 target 即可，否则就无法凑成。
而对于背包问题的遍历其实就是上面提到的一维和二维的情况；但是二维的情况明显更好：二维数组是从后向前遍历的，而这个最大值是在哪里出现的呢？恰好是最后一列中，所以在每次遍历完一层之后其实可以判断这个值是否达到了 target，如果出现就可以直接返回 true 而不需要继续遍历。
比如 [1,5,11,5] 在遍历到第三层的时候其实就已经得到 11 了。
这里将两种遍历方式的代码都提供出来。
<3> 代码
二维遍历方式：
java">class Solution {
public boolean canPartition(int[] nums) {
int length = nums.length; // 输入集合的长度
int sum = 0; // 集合的总和
int target = 0; // 集合总和的一半
for (int i : nums) sum += i;
if (sum % 2 != 0 || nums.length < 2) return false;
target = sum / 2;
int[][] dp = new int[target + 1][length];
// 初始化 dp 数组
for (int i = 0; i < dp.length; i++) {
if (i > nums[0]) dp[i][0] = nums[0];
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (i >= nums[j]) {
dp[i][j] = Math.max(dp[i][j - 1],
dp[i - nums[j]][j - 1] + nums[j]);
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
return dp[target][length - 1] == target;
}
}
一维遍历方式：
java">class Solution {
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return false;
int n = nums.length;
int sum = 0;
for(int num : nums) {
sum += num;
}
//总和为奇数，不能平分
if(sum % 2 != 0) return false;
int target = sum / 2;
int[] dp = new int[target + 1];
for(int i = 0; i < n; i++) {
for(int j = target; j >= nums[i]; j--) {
//物品 i 的重量是 nums[i]，其价值也是 nums[i]
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
//剪枝
if(dp[target] == target)
return true;
}
return dp[target] == target;
}
}
