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

• 原题链接：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));
    }
}