目录
- 题目
- 1- 思路
- 2- 实现
- ⭐152. 乘积最大子数组——题解思路
- 3- ACM 实现
题目
- 原题连接: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));}
}