Day 42

01. 背包问题 - 二维

<1> 01 背包问题

有 n 个物品和最多能装重量为 w 的背包，第 i 件物品的重量为 weight[i]，得到的价值是 value[i]，那如何将这些物品装入背包能获取最大的价值呢？

背包问题的一个很经典的 求最值 的问题，但因为其动态规划的过于的经典，很多朋友其实忽略了它的暴力解法，每一件物品只有两种状态：取或者不取，所以通过 回溯算法 将所有的情况遍历出来，可以求得最终的结果。

回溯算法示例：

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(2ⁿ)。

<2> 动态规划优化

利用回溯算法解题的时间复杂度达到了 指数 级别，所以必须要考虑优化的方法。

因为本题的最优解收到 两个维度 的限制，一个是 背包的容量，一个是 选取的物品的重量（这个重量又被能选择哪些物品所影响），在这两个内容的限制下去求得最优的价值，所以在设计 dp 数组的时候也要同时将这两个因素考虑在内。

在设计 dp 数组的时候考虑的就是在 某个背包容量下，选取某些物品 能达到的最优价值总和；那 dp[i][j] 就是从下标为 0 到 i 的范围内任意取，放到容量为 j 的背包里，能收获的 最大价值 是多少。

这样就可以开始确定递推公式了：要紧扣两个限制条件，一个物品仅仅有两种情况：

1. 不取这个物品，那此时价值最大的情况就是 dp[i - 1][j]，也就是在 这个容量下 取得的范围限制在 0 到 i - 1。
2. 取这个物品，但也要注意是在 这个容量下 去取的，也就是
   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，比如上面那个例子，初始化之后的结果就是：

// 遍历第一行
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]) 行为背包的容量，列为选取的物品；这两个其实就对应着两种遍历顺序：先遍历物品还是先遍历背包？

其实两种都是可以的，这两种情况推出一个节点所需要的数据都在 左上角，不影响公式的推导，但因为大多数都是先遍历物品，而且在含义上也更易理解，所以平时建议写的时候先去遍历物品，对于先遍历背包的能够理解和写出代码即可。

那现在写出代码：

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. 背包问题 - 一维

💡 相较于二维的方法，我认为一维的方法不止是在写法上，也是在性能上的一种优化。

可以观察一下上面的推导中的这一部分：

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，这就是新得到的递归公式。

写出代码

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 <= 200
• 1 <= nums[i] <= 100

<2> 笔记

这道题是背包问题的一个经典的实例问题，其实一开始看到这个题的时候并没有想到往背包方向靠的思路，而是当成了组合问题去做，但是在写的时候突然想到，这不就是 找一个子集，使得它们的和等于原集合和的一半 嘛？

再继续深入的想一下，如何才能凑出这个原集合的和的一半值呢？为了好表述这里将这个值设为 target，只考虑子集的和 小于或者等于 target 的情况，这个问题就可以转化为：

从集合中的所有元素中选取元素，刨去大于 target 的那部分，它们的和的最大值能否达到 target？

是不是感觉和背包问题有点像了？这个 target 就是限制最大值的指标，集合中的元素的大小（选取范围）就是限制的另一个部分，这不正是背包问题的 两个限制条件 嘛？再继续类比，这个 target，其实就是 背包的容量，集合中的元素就是物品，其重量和价值 都是 nums[i]。

将其转换成背包问题去做，只需要判断最右下角的那个元素是否 等于 target 即可，否则就无法凑成。

而对于背包问题的遍历其实就是上面提到的一维和二维的情况；但是二维的情况明显更好：二维数组是从后向前遍历的，而这个最大值是在哪里出现的呢？恰好是最后一列中，所以在每次遍历完一层之后其实可以判断这个值是否达到了 target，如果出现就可以直接返回 true 而不需要继续遍历。

比如 [1,5,11,5] 在遍历到第三层的时候其实就已经得到 11 了。

这里将两种遍历方式的代码都提供出来。

<3> 代码

二维遍历方式：

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;}
}

一维遍历方式：

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;}
}