【Hot100】LeetCode—416. 分割等和子集

---

题目

• 原题连接：416. 分割等和子集

---

1- 思路

理解为背包问题

• 思路： 能否将均分的子集理解为一个背包，比如对于 [1,5,11,5]，判断能否凑齐背包为 11 的容量
• 在本题中，背包中的物品是不可以重用的

1.定义 dp 数组

• dp[j] 代表容量为 j 的数组的最大价值，在本题中，容量就是价值。重量为 5 的石头，价值就是 5
• 可划分条件：dp[target] == target 也就是装满 target 的最大价值刚好是 target 这时候就可以划分

2.递推公式

• dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i]) ——> 在本题目中 weight 和 value 是一个东西

3.初始化

---

2- 实现

⭐152. 乘积最大子数组——题解思路

class Solution {public boolean canPartition(int[] nums) {// 求targetint sum = 0;for(int s:nums){sum+=s;}//总和为奇数，不能平分if(sum % 2 != 0) return false;int target = sum / 2;// 1. 定义dpint[] dp = new int[target+1];// 2. 递推公式// dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);// 3.初始化，都为 0dp[0] = 0;// 4. 先遍历物品，后遍历背包(逆序)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[j] == target){return true;}}}return false;}
}

---

3- ACM 实现

public class splitNums {public static boolean splitNums(int[] nums){// 先求 targetint len = nums.length;int sum = 0;for(int i:nums){sum+=i;}if(sum%2==1) return false;int target = sum/2;// 1. 定义 dp 数组int[] dp = new int[target+1];// 2. 递推公式// dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);dp[0] = 0;// 3.初始化// 4. 遍历顺序，先遍历物品后遍历背包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[j] == target) {return true;}}}return false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组长度");int n = sc.nextInt();int[] nums = new int[n];for(int i = 0 ; i < n ; i++){nums[i] = sc.nextInt();}System.out.println("结果是"+splitNums(nums));}
}