代码随想录算法训练营第四十二天| 01背包问题（二维、一维）、416.分割等和子集

系列文章目录

---

---

动态规划：01背包理论基础

(1)输入读取方法：

1. Scanner sc = new Scanner(System.in);String str = sc.nextLine();int m = Integer.parseInt(str.split(" ")[0]);int n = Integer.parseInt(str.split(" ")[1]);//将String[]数组通过stream流转换成int[]数组int[] weights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(/*s->Integer.parseInt(s)*/Integer::parseInt).toArray();int[] values =Arrays.stream(sc.nextLine().split(" ")).mapToInt(new ToIntFunction<String>() {@Overridepublic int applyAsInt(String value) {return Integer.parseInt(value);}}).toArray();
   

2. Scanner sc = new Scanner(System.in);// 读取背包容量和物品数量int m = sc.nextInt();int n = sc.nextInt();sc.nextLine(); // 消耗掉输入缓冲区的换行符// 读取物品重量和价值int[] weights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] values = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
   

3. // 获取输入数据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();}
   

①二维数组

（1）确定dp数组及其含义：
表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
（2）确定递推关系

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

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

代码如下：

import java.util.Arrays;
import java.util.Scanner;
import java.util.function.ToIntFunction;public class BagProblem {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();int m = Integer.parseInt(str.split(" ")[0]);int n = Integer.parseInt(str.split(" ")[1]);//将String[]数组通过stream流转换成int[]数组int[] weights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(/*s->Integer.parseInt(s)*/Integer::parseInt).toArray();int[] values =Arrays.stream(sc.nextLine().split(" ")).mapToInt(new ToIntFunction<String>() {@Overridepublic int applyAsInt(String value) {return Integer.parseInt(value);}}).toArray();//确定dp数组下标及含义:dp[i][j] 表示从下标为0-i的物品里任取，放到容量为j的背包中，价值总和最大为多少int[][] dp = new int[m][n+1];//需要考虑容量和物品数量为0的情况//dp数组初始化for (int i = 0; i < m; i++) {//列初始化dp[i][0] = 0;}for (int j = weights[0]; j <= n; j++) {//行初始化dp[0][j] = values[0];}//确定遍历顺序（先遍历物品再遍历容量或者先遍历容量再遍历背包都行）//①先遍历物品再遍历容量for (int i = 1; i < m; i++) {for (int j = 1; j <= n; j++) {/*** 当前背包的容量都没有当前物品i大的时候，是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/if(j<weights[i]){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 - weights[i]] + values[i]);}}}System.out.println(dp[m-1][n]);}
}

②一维数组（滚动数组）

（1）确定dp数组及其含义：
在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
（2）确定递推关系

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

（3）考虑初始化
dp[0]=0，因为背包容量为0所背的物品的最大价值就是0。那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？看一下递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

import java.util.Arrays;
import java.util.Scanner;
public class BagProblem {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();sc.nextLine();//接收换行符int[] weights = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] values = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();//确定dp数组及含义(背包容量为j的背包所能装的最大价值int[] dp = new int[n + 1];//dp数组初始化dp[0] = 0;//当背包容量为0时，最大价值也为0for (int i = 0; i < m; i++) {//遍历物品for (int j = n; j >= 0; j--) {//遍历容量（倒序遍历）if (j < weights[i]) {dp[j] = dp[j];} else {dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}}}System.out.println(dp[n]);}
}

---

416. 分割等和子集

①回溯法（超时）

import java.util.Arrays;public class SplitEqualSumSubsets {public static void main(String[] args) {int[] nums = {3,3,3,4,5};Solution solution = new Solution();boolean answer = solution.canPartition(nums);System.out.println(answer);}
}class Solution {int sum = 0;int tempSum = 0;public boolean canPartition(int[] nums) {for (int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum % 2 != 0) return false;//如果总和为奇数，则无法分割为两个等和子集//对数组从小到大排序Arrays.sort(nums);return backTracking(nums, 0);}public boolean backTracking(int[] nums, int startIndex) {//确定回溯函数的参数及返回值//确定回溯函数终止条件if (tempSum == sum / 2) return true;if (tempSum > sum / 2) {return false;}//确定单层递归逻辑boolean answer1 = false;for (int i = startIndex; i < nums.length; i++) {tempSum += nums[i];answer1 = backTracking(nums, i + 1);if(answer1)return true;// 如果找到一个可行解，立即返回，不再往下遍历tempSum -= nums[i];//回溯}return answer1;}
}

②动态规划（01背包）

未剪枝版

class Solution {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;//确定dp数组含义（容量为j的背包，放进0~i任意物品后，背的最大重量。int target = sum / 2;int[] dp = new int[target + 1];//dp数组初始化dp[0] = 0;for (int i = 0; i < nums.length; i++) {//先遍历物品for (int j = target; j >= 0; j--) {//倒序遍历背包容量if (j < nums[i]) {dp[j] = dp[j];} else {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//System.out.print(dp[j]);}//System.out.println();}return dp[target] == target;//如果背包装满了，即能找到等和子集}
}

剪枝版

class Solution {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;//确定dp数组含义（容量为j的背包，放进0~i任意物品后，背的最大重量。int target = sum / 2;int[] dp = new int[target + 1];//dp数组初始化dp[0] = 0;for (int i = 0; i < nums.length; i++) {//先遍历物品for (int j = target; j >= 0; j--) {//倒序遍历背包容量if (j < nums[i]) {dp[j] = dp[j];} else {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//System.out.print(dp[j]);}//System.out.println();//剪枝一下，每一次完成内层的for-loop，立即检查是否dp[target] == target，优化时间复杂度if (dp[target] == target) return true;}return dp[target] == target;//如果背包装满了，即能找到等和子集}
}