【力扣一刷】代码随想录day42（动态规划part4 - 背包问题专题：卡码网46.携带研究材料、416.分割等和子集 ）

目录

【卡码网46. 携带研究材料】

方法一  01背包问题 - 二维数组

方法二  01背包问题 - 一维数组

【416. 分割等和子集】

方法一  暴力回溯  ->  超时

方法二  动态规划（01背包问题）

方法一  01背包问题 - 二维数组

思路：

1、确定 dp[i][j] 的含义

dp[i][j] 是指从 0 ~ i 件物品中选部分物品放入容量为 j 的背包中能产生的最大价值。

2、确定递推关系

• 容量不够：一定放不下，直接返回不放 i 的最大价值
• 容量够：根据两种方案的价值做选择，选价值大的
  • 不放i：相当于在 0 ~ (i-1) 件物品中选择，容量不变
  • 放i：在确定放 i 的前提下（腾出空间给 i ），获取背包能产生的最大价值，再加上 i 的价值

3、考虑初始化

• 初始化第一行：对应物品0，如果背包容量不够，则设置为0，如果够，则设置为values[0]
• 初始化第一列：对应背包容量0，则无论是什么物品都放不下，不能产生任何价值，直接为默认值0即可

输入：M=3，N=4

weights = [1, 3, 4]

values = [15, 20, 30]

输出：35

bagValue矩阵：

          0     1      2      3      4

0        0    15    15    15    15    
1        0    15    15    20    35    
2        0    15    15    20    35

import java.util.*;public class Main{public static void main (String[] args) {// 获取输入数据Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] weights = new int[m];for (int i = 0; i < m; i++){weights[i] = sc.nextInt();}int[] values = new int[m];for (int i = 0; i < m; i++){values[i] = sc.nextInt();}// 定义背包问题的二维数组int[][] bagValue = new int[m][n+1]; // 行对应材料，列对应背包容量// 初始化第一行(第一列不需要初始化了，因为容量为0则无法装入任何物品，价值为0)for (int j = 0; j < n+1; j++){// 如果第一件物品所占的空间 > 背包容量，则无法放入，价值为0// 如果第一件物品所占的空间 ≤  背包容量，则可以放入，价值为物品0的价值if (j >= weights[0]) bagValue[0][j] = values[0];}// 开始递推for (int i = 1; i < m; i++){for (int j = 1; j < n+1; j++){// 容量不够if (weights[i] > j) { bagValue[i][j] = bagValue[i-1][j]; // 一定放不下，直接返回不放i的最大价值continue;}// 容量够// 不放i:相当于在0-(i-1)件物品中选择，容量不变int no = bagValue[i-1][j];// 放i:在确定放i的前提下（腾出空间给i），获取背包能产生的最大价值，再加上i的价值int yes = bagValue[i-1][j-weights[i]] + values[i];// 根据两种方案的价值做选择，选价值大的bagValue[i][j] = Math.max(no, yes);}}System.out.println(bagValue[m-1][n]);}
}

易错点总结：

1、定义二维矩阵的时候，行数M对应M件物品，列数N+1对应背包容量，因为还需要考虑容量为0的情况。

2、初始化第一行时要考虑背包容量和第0件物品所占空间的大小关系，可以直接从物品0所占空间对应的背包容量开始遍历进行初始化，也可以从背包容量0开始遍历加以判断再进行初始化。

3、在递推时，也要考虑背包容量和第0件物品所占空间的大小关系，即能不能放物品 i ，不能放直接返回不放的最大价值，能放要考虑不放 i 和放 i 哪个价值大。

4、卡码网的输入输出问题，以及记得要import和写main函数

import java.util.*;public class Main{public static void main (String[] args)

• 时间复杂度：O(M × N)，遍历一次二维数组
• 空间复杂度：O(M × N)，额外的二维数组开销

方法二  01背包问题 - 一维数组

思路：和二维数组的思路基本一致，但是使用一维数组可以大大减小空间复杂度。

区别：遍历过程会对一维数组进行滚动赋值，即不断根据一维数组的旧值更新新值。

• 对于j < weights[i]，这个现象没有影响，因为容量不足，肯定不需要放入第 i 个物品，就相当于从0 ~ i -1个物品中选择物品放入背包而产生的最大价值，直接就是原来的值；
• 对于 j >= weights[i]，除了初始值外（对应不放 i 的情况），还需要计算放 i 的情况，计算时需要获取一维数组左边的元素 dp[ j - weights [i]]（对应二维数组的dp[i - 1][ j - weights [i]]）进行计算，如果左边的值在从左到右遍历时已经更新过，则dp[ j - weights [i]]不是原来二维数组对应的dp[i - 1][ j - weights [i]]，而是dp[i][j - weights [i]]，这明显不对，因此要倒序遍历一维数组，先更新右边的，再更新左边的。

import java.util.*;public class Main{public static void main (String[] args) {// 获取输入数据Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] weights = new int[m];for (int i = 0; i < m; i++){weights[i] = sc.nextInt();}int[] values = new int[m];for (int i = 0; i < m; i++){values[i] = sc.nextInt();}// 定义一维数组，利用滚动数组的方式代替二维矩阵，减小空间复杂度int[] dp = new int[n+1];for (int i = 0; i < m; i++){for (int j = n; j > 0; j--){if (j >= weights[i]){dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]);} }}System.out.println(dp[n]);}
}

• 时间复杂度：O(M×N)
• 空间复杂度：O(N)

【416. 分割等和子集】中等题

思考：

例子1：【1，2，3，4，5】，和为15，奇数，分割后两个子集的和不可能相等

例子2：【1，1，100】，和为102，偶数，无法按要求分割

方法一  暴力回溯  ->  超时

class Solution {List<Integer> path = new LinkedList<>();int pathSum = 0;public boolean canPartition(int[] nums) {int sum = 0;for (int i = 0; i < nums.length; i++){sum += nums[i];}if (sum % 2 != 0) return false;Arrays.sort(nums);return backtracking(nums, 0, sum/2);}public boolean backtracking(int[] nums, int start, int target){if (start >= nums.length) return false;if (pathSum == target) return true;for (int i = start; i < nums.length; i++){if (i > start && nums[i] == nums[i-1]) continue;path.addLast(nums[i]);pathSum += nums[i];if (backtracking(nums, i+1, target)) return true;path.removeLast();pathSum -= nums[i];}return false;}
}

方法二  动态规划（01背包问题）

思路：将分割问题转化为01背包问题，将每个nums[i]看作是一个物品，物品的价值和重量都是nums[i]，遍历过程考虑放还是不放物品 i ，看是否能将容量为 sum / 2 的背包恰好装满。最后，获取一维数组中 j = sum / 2的最大价值 dp(sum / 2)，如果最大价值就是 sum / 2，说明恰好能装满，返回true，否则返回false。

---

步骤：

1、确定dp[j]的含义

容量为j的书包能产生的最大价值

2、确定递推关系

当容量足够存储第 i 个物品时，dp[j] = Math.max(dp[j], dp[j-weights[i]] + values[i]) ，否则取默认值即可。

3、确定初始值

dp[0]即容量为0能产生的最大价值，即也是0

原始版

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum += num;if (sum % 2 != 0) return false;int[] dp = new int[sum+1];for (int i = 0; i < nums.length; i++){for (int j = sum / 2; j >= nums[i]; j--){ // 背包容量大于物品重量才考虑放的情况dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}return dp[sum/2] == sum/2;}
}

优化版

1、根据需要，缩短数组长度

2、中途剪枝

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum += num;if (sum % 2 != 0) return false;int[] dp = new int[sum/2+1]; // 数组长度只要能计算到容量为sum/2即可，加上容量0，长度为sum/2+1for (int i = 0; i < nums.length; i++){for (int j = sum / 2; j >= nums[i]; j--){ // 背包容量大于物品重量才考虑放的情况dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}// 剪枝：遍历中途可以检查是否出现背包恰好装满到sum/2的情况if (dp[sum/2] == sum/2) return true;}return dp[sum/2] == sum/2;}
}

• 时间复杂度：O(n²)
• 空间复杂度：O(n)