【代码训练营】day41 | 01背包问题 416. 分割等和子集

所用代码 java

01背包理论

背包最大重量为：4

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

暴力：O(2^n)

动态规划：

1、二维dp数组 dp[i] [j]

• dp数组含义：[0, i]物品，任取放进容量为j的背包里的最大价值

• 递推公式：

  • 不放物品i ：dp[i-1] [j]
  • 放物品i：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[i] [j] i：物品 j：背包容量(0 1 2 3 4 )

	0	1	2	3	4
物品0	0	15	15	15	15
物品1	0			n => 由上和左上推出
物品2	0

• 遍历顺序：对于二维数组的01背包，先背包后物品，先物品后背包都可以
• 打印dp数组：

具体代码：

public class 背包01 {public static void main(String[] args) {int[] weight = {1,3,4};int[] value = {15,20,30};int bagSize = 4;bagProblem01(weight,value,bagSize);}public static void bagProblem01(int[] weight, int[] value, int bagSize){int goods = weight.length; // 物品数量int[][] dp = new int[goods][bagSize + 1];// 初始化 - 只有一个物品的时候，不管背包多大，加载都是该物品的价值for (int j = 0; j <= bagSize; j++) {dp[0][j] = value[0];}// 背包i在背包容量为0的时候，最大价值为0for (int i = 0; i < goods; i++) {dp[i][0] = 0;}// 先遍历背包，再遍历物品for (int i = 1; i < goods; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]){// 当背包容量没有当我物品那么大时，就是放不下物品，最大的重量为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]] + 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();}}
}
打印结果：
0	15	15	15	15	
0	15	15	20	35	
0	15	15	20	35

2、一维dp数组dp[j] - 滚动数组

• dp[j]：容量为j的背包最大价值为dp[j] i为物品
• 递推公式：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
• 初始化：dp[0] = 0 其他非负里面的最小值，如0。
• 遍历顺序：
  • 先遍历物品，再遍历背包
  • 倒序遍历，保证每个物品只被添加了一次。
• 打印dp数组

public static void bagProblem1(int[] weight, int[] value, int bagSize){int goods = weight.length; // 物品数量int[] dp = new int[bagSize + 1];// 初始化Arrays.fill(dp, 0);// 先遍历背包，再遍历物品for (int i = 0; i < goods; i++) {// j >= weight[i] 保证从右向左遍历的时候dp[j-weight[i]]不会越界for (int j = bagSize; j >= weight[i]; j--){dp[j] = Math.max(dp[j-1], dp[j-weight[i]] + value[i]);}}// 打印for (int MaxValue : dp) {System.out.print(MaxValue + "\t");}
}

分割等和子集 LeetCode 416

题目链接：分割等和子集 LeetCode 416 - 中等

思路

试了滑动窗口，不行。滑动窗口适合连续的数。

---

应该抽象为一个背包，背包的容量为数组和的一半，只要装下一半，另一半肯定可以。

• dp[j] ：容量为j的背包能装下的最大价值为dp[j]
• 递推公式：dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]) 重量和价值是相同的
• 初始化：dp[0] = 0；背包不可能是负数，需初始成非负整数的最大值 0
• 遍历方向：从右到左
• 打印dp数组

一维数组：

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;// dp数组初始为0int[] dp = new int[target + 1];// 物品for (int i = 0; i < nums.length; i++) {for (int j = target; j >= nums[i]; j--){dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);}}// 看一下最后一个数是不是targetreturn dp[target] == target;}
}

二维数组：

• dp[i] [j] ： 前i个数，其总价值不超过j的最大价值为dp[i] [j] j代表的是背包重量
• 递推公式：dp[i] [j] = Math.max(dp[i-1] [j], dp[i-1] [j - nums[i]] + nums[i]);
• 初始化：小于num[0]的不能装，初始化为0，其余为nums[0]

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;int[][] dp = new int[nums.length][target + 1];// 初始化，只有一个物品时的重量for (int j = 0; j <= target; j++) {dp[0][j] = j > nums[0] ? nums[0] : 0;}// 物品数量for (int i = 1; i < nums.length; i++) {// 背包容量，背包容量0，默认不能装for (int j = 1; j <= target; j++) {// 不能装下物品，最大值就是前一个值if (j < nums[i]){dp[i][j] = dp[i-1][j];}else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - nums[i]] + nums[i]);}
//                System.out.print("dp="+dp[i][j] + "\t");}
//            System.out.println();}return dp[nums.length-1][target] == target;}
}

总结

本题主要是分析，只要把该题分析出来是背包问题的话，照着这个思路就非常的简单。

第二点就是二维数组在初始化的适合需要注意，背包重量小于nums[0]的数是没法装的，需初始化为0。

另外还有一种思路：

• dp[i] [j] ： 从[0, i]区间中挑选一些正整数，每个数只能用一次，这些数的和恰好为 j
• 递推公式：dp[i] [j] = dp[i - 1] [j] || dp[i - 1] [j - nums[i]]
• 初始化：在num[0] < target 的情况下，第一个数只能让容积为自己的背包填满：dp[0] [num[0]] = true

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) sum+=num;if (sum % 2 == 1) return false;// target 相当于背包的容量int target = sum / 2;boolean[][] dp = new boolean[nums.length][target + 1];// 初始化，填满第一行的dp[0][nums[0]] 只有nums[0]本身if (nums[0] < target) dp[0][nums[0]] = true;//        System.out.print("dp[0] = " + Arrays.toString(dp[0]));
//        System.out.println();// 外层遍历物品数量for (int i = 1; i < nums.length; i++) {// 内层遍历背包for (int j = 0; j <= target; j++) {// 先取上一次的结果，后面进行修正dp[i][j] = dp[i-1][j];// 如果某个物品的重量恰好等于背包重量，则满足条件// 所以这一列的值都为trueif (nums[i] == j){dp[i][j] = true;
//                    System.out.print("***="+dp[i][j] + "\t\t");continue;}// 如果该物品小于背包的重量，就判断能否加入新的物品// dp[i-1][j]表示不放入背包，如果前面有满足条件，后面就一定可以满足// dp[i-1][j-nums[i]]表示放入背包，放入后判断放入背包的区间有没有满足条件的，就是左上if (nums[i] < j){dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];}
//                System.out.print("dp="+dp[i][j] + "\t\t");}
//            System.out.println();}return dp[nums.length-1][target];}
}