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

一、01背包问题二维

二维数组，一维为物品，二维为背包重量

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int bag = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i=0; i<n ; i++){weight[i] = scanner.nextInt();}for(int j=0; j<n ; j++){value[j] = scanner.nextInt();}int[][] dp = new int[n][bag+1];for(int j=weight[0]; j<=bag ; j++){dp[0][j] = value[0];}for(int i = 1 ; i<n ; i++){for(int j=0; j<=bag ; j++){if(j<weight[i]){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]);}}}System.out.println(dp[n - 1][bag]);}
}

二、01背包问题一维

在一维数组上更新，pd[j] 为容量为j的背包容纳的最大价值。

第一层循环是每个物品，第二层循环要从背包容量向前循环到当前物品重量，更新时判断【当前容量最大价值】和【放入当前物品后的总价值】的最高值。

import java.util.Scanner;public class Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int bag = scanner.nextInt();int[] weight = new int[n];int[] value = new int[n];for(int i=0; i<n ; i++){weight[i] = scanner.nextInt();}for(int j=0; j<n ; j++){value[j] = scanner.nextInt();}int[] dp = new int [bag+1];for (int i = 0; i < n; i++) {for (int j = bag; j >=  weight[i]; j--) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bag]);}
}

三、416. 分割等和子集

利用背包问题的思路，看能否装满sum/2的背包，物品的重量和价值一样都是元素的数值

class Solution {public boolean canPartition(int[] nums) {if(nums ==null || nums.length < 2) return false;int sum = 0;for(int num : nums){sum += num;}if(sum%2 == 1) return false;int target = sum/2;int[] 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]);}if(dp[target]==target) return true;}return dp[target]==target;}
}