【DP】子集背包问题｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目概述

LeetCode 416. 分割等和子集

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
 


示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
复制代码

题干分析

背包问题大致的描述：

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i], 价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

那么对于这个问题，可以先对集合求和，得出 sum，把问题转化为背包问题：

给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？

动态规划标准套路：

1. 第一步要明确：状态 和 选择
2. 第二步要明确：dp 数组的定义
3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 第一步要明确：状态 和 选择

1. 状态：“背包的容量” 和 “可选择的物品”
2. 选择：“装进背包” 或者 “不装进背包”

2. 第二步要明确：dp 数组的定义

1. dp数组的定义：dp[i][j] = x 表示对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。

   比如，dp[4][9] = true, 其含义为：对于容量为 9 的背包，若只使用前 4 个物品，则存在一种方法恰好把背包装满。

2. 最终答案：dp[N][sum / 2]

3. base case：dp[..][0] = true 和 dp[0][..] = false

   因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没颁发装满背包。

3. 第三步：根据 “选择”，思考状态转移的逻辑

1. 如果不把 nums[i] 算入子集，或者说不把第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i - 1][j]，继承之前的结果。

2. 如果把 nums[i] 算入子集，或者说把第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于 dp[i - 1][j - nums[i - 1]]。

二、思路实现

    // Time: O(n * sum), Space: O(sum), Faster: 26.77%
    public boolean canPartition(int[] nums) {

        int sum = 0;
        for (int num : nums) sum += num;

        // 和为奇数时，不可能划分成两个和相等的结合
        if (sum % 2 != 0) return false;
        int n = nums.length;
        sum = sum / 2;
        boolean [][] dp = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; ++i) dp[i][0] = true;

        // 开始状态转移
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= sum; ++j) {
                if (j - nums[i - 1] < 0) {
                    // 背包容量不足，肯定不能装入第 i 个物品
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 装入或不装入背包
                    // 看看是否存在一种情况能够恰好装满
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][sum];
    }
复制代码

优化：

    // Time: O(n * sum), Space: O(sum), Faster: 71.34%
    public boolean canPartition2(int[] nums) {

        int sum = 0;
        for (int num : nums) sum += num;

        // 和为奇数时，不可能划分成两个和相等的结合
        if (sum % 2 != 0) return false;
        int n = nums.length;
        sum = sum / 2;

        boolean [] dp = new boolean[sum + 1];
        dp[0] = true;

        // 开始状态转移
        for (int i = 0; i < n; ++i) {
            for (int j = sum; j >= 0; --j) {
                if (j - nums[i] >= 0)
                    dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
复制代码