一、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;}
}