代码随想录算法训练营第四十二天|01背包问题，你该了解这些！、01背包问题，你该了解这些！ 滚动数组 、416. 分割等和子集

01背包问题，你该了解这些！

• 题目链接：代码随想录

二维数组解决0-1背包问题

• 解题思路：
  1.dp[i]|[j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
  2.确定递推公式：不放物品i，放物品i dp[i]|[j] = max(dp[i - 1]|[j], dp[i - 1]|[j - weight[i]] + value[i]);
  3.初始化；当前处理的结果都是由左上角推出来的，所以只用初始化左上和即可，即第一行和第一列
  4.确定遍历顺序：本题无论是先遍历背包还是先遍历物品都可以

• 图像理解

  

public class BagProblem {public static void main(String[] args) {int[] weight = {1,3,4};int[] value = {15,20,30};int bagSize = 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* @param weight  物品的重量* @param value   物品的价值* @param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){//1.创建dp数组//dp[i][j] 表示从0-i个物品中挑选物品，放入容量为j的背包中，所取得的最大价值int length = weight.length;int[][] dp = new int[length][bagSize + 1];//2.初始化数据，只初始化第一行，第一列默认初始化为0for (int i = weight[0]; i < dp.length; i++) {//i为物品0的重量dp[0][i] = value[0];}//3.遍历dp数组for (int i = 1; i < weight.length; i++) {for (int j = 1; j < bagSize + 1; 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]);}}}for (int i = 0; i < length; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println("\n");}}
}

01背包问题，你该了解这些！ 滚动数组

• 题目链接：代码随想录

一维数组解0-1背包问题

• 每次放入一个物品之后，求得的dp数组就是能放下一个物品的容量的最大价值

  因此不用太考虑放入一个物品后前后容量关系，就考虑一个个将物品完全放入背包即可

• 解题思路：
  1.dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
  2.dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  3.dp数组初始化的时候，都初始为0。这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了
  4.先遍历放入物品，再遍历不同容量的背包，从后向前遍历

• 图像理解：

  开始向背包里放的时候

  

public class BagProblemOneArray{public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){// int wLen = weight.length;// //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值// int[] dp = new int[bagWeight + 1];// //遍历顺序：先遍历物品，再遍历背包容量// for (int i = 0; i < wLen; i++){//     for (int j = bagWeight; j >= weight[i]; j--){//         dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);//     }// }// //打印dp数组// for (int j = 0; j <= bagWeight; j++){//     System.out.print(dp[j] + " ");// }int goodsLength = weight.length;//背包的个数int[] dp = new int[bagWeight + 1];//dp数组for (int i = 0; i < goodsLength; i++) {for (int j = bagWeight; j >= weight[i]; j--) {dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);}}for (int i = 0; i <= bagWeight; i++) {System.out.print(dp[i] + " ");}}
}

416. 分割等和子集

• 题目链接代码随想录

本题因为元素只能用一次，因此是0-1背包问题
整体思路，找到元素价值量能恰好装进符合价值sum/2的容量的背包
本题每个商品价值量 = 重量

• 解题思路：

  1. dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。
     那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了
  2. 递推公式：背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
  3. 初始化：dp数组都初始化为0
  4. 从后向前

• 图像理解:

  

public boolean canPartition(int[] nums) {//dp数组// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了    int[] dp = new int[10001];int sum = 0;//计算总和for (int i = 0; i < nums.length; i++) {sum += nums[i];}if(sum % 2 == 1){return false;}//为奇数，分成两个集合，必不成立int target = sum / 2;//0-1背包for (int i = 0; i < nums.length; i++) {for (int j = target; j >= nums[i];j--) {//j从target开始，因为背包目标重量为即最后求解的结果dp[j] = Math.max(dp[j],dp[j - nums[i] + nums[i]]);}}if(dp[target] == target){return true;}return false;
}