目录
- 1- 思路
- 题目识别
- 动规五部曲
- 2- 实现
- ⭐416. 分割等和子集——题解思路
- 3- ACM 实现
- 原题链接:416. 分割等和子集
1- 思路
题目识别
- 识别1 :等和子集
动规五部曲
思路:
- 首先求
sum
,如果sum
是一个奇数 则 不能进行分割 。 - 之后根据 0 1 背包的递推公式
dp[j] = Math.max(dp[j] , dp[j-weights[i]] + values[i]);
2- 实现
⭐416. 分割等和子集——题解思路
class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int i:nums){sum+=i;}if(sum%2!=0) return false;int half = sum/2;// 转换为是否可以填满背包 为 half 的背包问题,商品为 nums//1. 定义 dp 数组int[] dp = new int[half+1];//2. 递推公式// 商品的重量小于 half ,填充// if(nums[i] < half) // 3. 初始化,全为 0// 0-1 背包的遍历顺序// 先物品for(int i = 0 ; i < nums.length ; i++){// 后背包for(int j = half ; j>=nums[i] ; j--){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[half] == half;}
}
3- ACM 实现
public class canPartition {public static boolean canPartition(int[] nums) {int sum = 0;for(int i:nums){sum+=i;}if(sum%2!=0) return false;int half = sum/2;// 转换为是否可以填满背包 为 half 的背包问题,商品为 nums//1. 定义 dp 数组int[] dp = new int[half+1];//2. 递推公式// 商品的重量小于 half ,填充// if(nums[i] < half)// 3. 初始化,全为 0// 0-1 背包的遍历顺序// 先物品for(int i = 0 ; i < nums.length ; i++){// 后背包for(int j = half ; j>=nums[i] ; j--){dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);}}return dp[half] == half;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}System.out.println("结果是"+canPartition(nums));}
}