代码随想录算法训练营第三十七天|01背包问题、分割等和子集

01背包问题

在这里插入图片描述

题目链接：46. 携带研究材料
文档讲解：代码随想录
状态：忘了

二维dp

问题1：为啥会想到i代表第几个物品，j代表容量变化？

动态规划中，每次决策都依赖于前一个状态的结果，在背包问题中每次取物品的操作都必须考虑当前背包容量是否足够。所以使用i代表第几个物品，j代表背包容量限定。而第i个物品取和不取直接影响到最大价值总和dp[i][j]。

因此，dp[i][j]可以表示为，在容量j的条件下，取第i个物品所能得到的最大价值总和。

动态转移方程：

每次状态转移，需要考虑当前背包容量是否足够容纳物品i：

如果当前物品i的重量 weight[i] 大于当前背包的容量j，则显然无法将物品i放入背包，因此 dp[i][j] 应该等于 dp[i-1][j]，即不拿当前物品i时的最优解。
如果当前物品i的重量 weight[i] 小于等于当前背包的容量j，则可以尝试将物品i放入背包（不能保证一定能放下）。此时，考虑两种情况：
- 不放入物品i，也就是物品i放不下，否则能放下的话肯定是放入物品i后总价值更高！即 dp[i][j]=dp[i-1][j]，和上面的情况一样！
- 放入物品i，能放下物品i，肯定是放入后价值更高，即dp[i][j] = dp[i-1][j - weight[i]] + value[i]，其中 value[i] 是物品i的价值。

考虑到上述情况，所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

二维dp题解：

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {// 创建dp数组int goods = weight.length;  // 获取物品的数量int[][] dp = new int[goods][bagSize + 1];// 初始化dp数组// 创建数组后，其中默认的值就是0// 当背包的容量大于等于第一个物品的重量时，才会将取第一个物品时最大价值设为第一个物品的价值for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}// 填充dp数组for (int i = 1; i < weight.length; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候，是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] = dp[i - 1][j];} else {/*** 当前背包的容量不确定可以放下物品i* 那么此时分两种情况：*    1、放不下,所以不放物品i*    2、放物品i* 比较这两种情况下，哪种背包中物品的最大价值最大*/dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}// 打印dp数组for (int i = 0; i < goods; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println("\n");}}//这种方法初始化时,初始化了一个(m+1)×(n+1)的二维数组，包含了额外的一行和一列，用来表示没有放入任何物品时的情况。public static void testWeightBagProblem2(int[] weight, int[] value, int bagSize) {// 创建dp数组int m = weight.length;  // 获取物品的数量int n = bagSize;int[][] dp = new int[m + 1][n + 1];  // 创建动态规划数组，行表示物品数量，列表示背包容量// 填充dp数组for (int i = 1; i <= m; i++) {  // 遍历物品for (int j = 1; j <= n; j++) {  // 遍历背包容量if (j < weight[i - 1]) {  // 如果当前背包容量小于当前物品的重量，则无法装入该物品dp[i][j] = dp[i - 1][j];  // 当前最优解等于上一个物品的最优解} else {  // 否则可以选择装入当前物品或者不装入当前物品，取两者中的最大值dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);// 不装入当前物品：dp[i - 1][j]// 装入当前物品：dp[i - 1][j - weight[i - 1]] + value[i - 1]// value[i - 1] 表示当前物品的价值}}}// 打印dp数组for (int i = 0; i <= m; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");  // 打印每个位置的最优值}System.out.println("\n");  // 换行}}

优化：

可以考虑用另一方式来定义dp[i][j]的含义，即dp[i][j] 表示考虑前i个物品，在背包容量为j时可以达到的最大价值。

那么dp[i][j]就可能从两种状态转换而来。

第一种是当前物品i放不下，那么dp[i][j]=dp[i−1][j]，也就是继承上一个状态的最优解
第二种是可以放当前物品i，那么dp[i][j]=dp[i−1][j−weight[i−1]]+value[i]，也就是在上一个状态的继承上加上当前物品i的价值

因此，可以的到递推公式：dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i]);

优化后题解：

// 使用了优化后的递推公式 dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
public static void testWeightBagProblem3(int[] weight, int[] value, int bagSize) {int length = weight.length;// 创建二维数组dp，dp[i][j]表示考虑前i个物品，在背包容量为j时的最大价值int[][] dp = new int[length + 1][bagSize + 1];// 遍历每个物品for (int i = 1; i <= length; i++) {// 遍历每个背包容量for (int j = 1; j <= bagSize; j++) {// 先假设不选第i个物品，继承上一个状态的最优解dp[i][j] = dp[i - 1][j];// 判断如果当前背包容量能够容纳第i个物品if (weight[i - 1] <= j) {// 考虑选择第i个物品后的最优解，这里要注意value[i - 1])是第i个物品的价值，因为第一行和第一列用0填充了,但是value数组是从索引0开始有意义的。dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);}}}
}

一维dp:

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);也就是上面优化后的代码。
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。此时，dp[j]的状态要么是上次取完物品i-1的状态，要么是加入物品i的状态。

 在取物品0的时候,dp[j]会进行第一轮更新[0  15  15  15	 15]在取物品1的时候,dp[j]会进行第二轮更新[0  15	 15	 20	 35]在取物品2的时候,dp[j]会进行第三轮更新[0  15	 15  20	 35]

所以递推公式为，dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

左边的 dp[j]：表示在更新当前容量 j 时，新的 dp[j] 值。
右边的 dp[j]：表示背包装不下物品i，所以继承上次容量为 j 时取完物品i-1的最大价值，即在未考虑物品 i 的情况下的最大价值。
右边的 dp[j - weight[i-1]] + value[i]：表示在当前更新之前，容量为 j - weight[i-1] 时的最大价值，加上当前物品 i 的价值。

为什么需要从后向前遍历？

在使用一维数组 dp 时，从后向前遍历容量 j 是为了避免在同一轮次中使用已经更新的值。这保证了每个物品 i 在更新时只被计算一次，不会重复使用。

举个例子：
物品 1: 重量 2，价值 3
物品 2: 重量 3，价值 4
背包容量为 5。

从前向后遍历：
我们从前向后遍历容量 j 来更新 dp 数组。看看会发生什么情况。

遍历第一个物品（重量 2，价值 3）：
j = 2:
dp[2] = max(dp[2], dp[2 - 2] + 3) = max(0, 0 + 3) = 3
更新后 dp = [0, 0, 3, 0, 0, 0]

j = 3:
dp[3] = max(dp[3], dp[3 - 2] + 3) = max(0, 0 + 3) = 3
更新后 dp = [0, 0, 3, 3, 0, 0]

j = 4:
dp[4] = max(dp[4], dp[4 - 2] + 3) = max(0, 3 + 3) = 6
更新后 dp = [0, 0, 3, 3, 6, 0]
从这里开始就出现问题了，求dp[4]的时候使用了更新后的dp[2]的值。

j = 5:
dp[5] = max(dp[5], dp[5 - 2] + 3) = max(0, 3 + 3) = 6
更新后 dp = [0, 0, 3, 3, 6, 6]，求dp[5]的时候使用了更新后的dp[3]的值。

遍历第二个物品。。。。（略）

从后向前遍历：
遍历第一个物品（重量 2，价值 3）：
j = 5:
dp[5] = max(dp[5], dp[5 - 2] + 3) = max(0, 0 + 3) = 3
更新后 dp = [0, 0, 0, 0, 0, 3]，这里使用的dp[2]是还没更新的值。
…（略）

一维dp代码：

    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize) {int[] dp = new int[bagSize + 1];for (int i = 0; i < weight.length; i++) {for (int j = bagSize; j >= weight[i]; j--) {//因为i在更新,所以max中的dp[j]都是上一层中的dp[j],所以隐式地实现了"dp[i - 1]一层拷贝到dp[i]"dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);//max中的dp[j]是取上一个物品时对应容量j的最大价值}}for (int j = 0; j <= bagSize; j++) {System.out.print(dp[j] + "\t");}}

416. 分割等和子集

在这里插入图片描述

题目链接：416. 分割等和子集
文档讲解：代码随想录
状态：感觉像碰运气做出来的。。

思路：

第一步读题：分割成两个子集，使得两个子集的元素和相等，那么可以考虑先求和再除以2，得到目标值。对于nums中的数字，尝试不同的取值求和，只要得到和为target说明一定可以分成两个和相等的子集。所以可以考虑使用背包解题。

第二步判断背包类型：

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

第三步：动规五部曲分析。

dp[j] 表示：容量为j的背包，所背的物品价值最大可以为dp[j]。在本题中就是取不同的值求得最大和dp[j]。本题中如果dp[j]=j就是满足条件了。
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
初始化，取第一个数字前，dp[j]都为0
确定遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
举例推导dp数组：如果dp[j] == j 说明，集合中的子集总和正好可以凑成总和j

题解：

// 一维dp实现
public boolean canPartition(int[] nums) {int sum = 0;// 计算数组总和for (int num : nums) {sum += num;}// 如果总和是奇数，不可能分成两个相等的子集if (sum % 2 == 1) {return false;}// 目标值是总和的一半int target = sum / 2;// 创建一维dp数组，dp[j]表示是否存在子集和为jint[] dp = new int[target + 1];// 遍历所有数字for (int i = 0; i < nums.length; i++) {// 倒序遍历所有可能的和for (int j = target; j > 0; j--) {// 如果当前数字小于等于目标和，更新dp数组if (nums[i] <= j) { // 刚开始没注意到这里, 其实最好写在for循环的判断条件中, 因为使用的数字肯定不能大于目标和dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}// 剪枝，只要有满足条件即可提前退出if (dp[target] == target) {return true;}}// 检查是否可以找到和为target的子集return dp[target] == target;
}

二维dp题解：

// 二维dp实现
public boolean canPartition(int[] nums) {int sum = 0;// 计算数组总和for (int num : nums) {sum += num;}// 如果总和是奇数，不可能分成两个相等的子集if (sum % 2 == 1) {return false;}// 目标值是总和的一半int target = sum / 2;// 创建二维dp数组，dp[i][j]表示前i个数能否组成和为jint[][] dp = new int[nums.length + 1][target + 1];// 遍历所有数字for (int i = 1; i <= nums.length; i++) {// 遍历所有可能的和for (int j = 1; j <= target; j++) {if (nums[i - 1] > j) {// 如果当前数字大于目标和，不能选当前数字，继承上一个状态的结果dp[i][j] = dp[i - 1][j];} else {// 否则，可以选择或者不选择当前数字，取两者的最大值dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);}}}// 检查是否可以找到和为target的子集return dp[nums.length][target] == target;
}