分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

方法一：0 - 1背包

算法思路：

背包问题为，有N件物品和一个最多能背重量为W的背包，第i件物品的重量是weight[i]，得到的价值是value[i]，每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

明确以下四点，才能把01背包问题套到本题上来（只能放入一次是01背包，能重复多次放入是完全背包）：

  • 背包的体积为sum / 2

  • 背包要放入的商品（集合里的元素），重量为元素的数值，价值也为元素的数值

  • 背包如果正好装满，说明找到了总和为sum / 2的子集

  • 背包中每一个元素是不可重复放入

确定可以套用，则动态规划五部曲：

  1. 确定dp数组以及下标的含义

    dp[i][j]代表可装物品为0 - i，背包容量为j的情况下，背包内容量的最大值。

  2. 确定递推公式

    当能放的下nums[i]的时候，比较放还是不放，谁的值比较大。

    if(j >= nums[i]){
               dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
           }else{
               dp[i][j] = dp[i - 1][j];
           }

  3. dp数组的初始化

    dp[0][i]表示不放物品，价值为0。

    dp[o][j]表示只放第一个物品，价值为nums[0]。

    for(int j = nums[0]; j <= target; j++){
                dp[0][j] = nums[0];
            }

  4. 确定遍历顺序

    先遍历物品i，再遍历背包j。

  5. 举例推导dp数组

    0 1 2 3 4 5 6 7 8 9 10 11
    0 0 1 1 1 1 1 1 1 1 1 1 1
    1 0 1 1 1 1 5 6 6 6 6 6 6
    2 0 1 1 1 1 5 6 6 6 6 6 11
    3 0 1 1 1 1 5 6 6 6 6 10 11

算法实现：

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num: nums){
            sum += num;
        }
        if(sum % 2 == 1){
            return false;
        }
        int target = sum / 2;
        int[][] dp = new int[nums.length][target + 1];
        for(int j = nums[0]; j <= target; j++){
            dp[0][j] = nums[0];
        }
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j <= target; j++){
                if(j >= nums[i]){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][target] == target;
    }
}

方法二：一维数组0 - 1背包

算法思路：

动态规划五部曲：

  1. 确定dp数组以及下标的含义

    dp[j]代表背包容量为j的情况下，背包内容量的最大值。

  2. 确定递推公式

    和二维数组不同，这里不用比较，因为j的范围使得nums[i]肯定能放下。

    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);

  3. dp数组的初始化

    dp[0]表示不放物品，价值为0。

    如果题目给的价值都是正整数，那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么0的下标就要初始化为负无穷。这样才能在递归中取得最大价值，而不会被出示值覆盖。

  4. 确定遍历顺序

    先遍历物品i，再遍历背包j，且内层for循环倒序。

    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]);
                }
            }

  5. 举例推导dp数组

    0 1 2 3 4 5 6 7 8 9 10 11
    0 1 1 1 1 5 6 6 6 6 10 11

代码实现：

class Solution {
    public boolean canPartition(int[] nums) {
        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]);
            }
        }
        return dp[target] == target;
    }
}

参考

代码随想录 - 分割等和子集