经典动态规划：子集背包问题

416. 分割等和子集

这个问题和之前我们分析的问题 划分为k个相等的子集 很像，只是本篇文章的问题是划分为 2 个相等的子集而已。关于「划分为k个相等的子集」的详细讲解可见 经典回溯算法：集合划分问题

本人也尝试过借鉴「划分为k个相等的子集」的思路去解决本问题，毫无意外的超时，本问题的数据量远大于它的数据量。所以，本篇文章将介绍如何利用动态规划的方法解决本问题

小建议：如果没有阅读过 经典动态规划：0-1 背包问题，请务必先去看懂，因为本篇文章是按照「0-1 背包」的思路框架来讲解的！

问题分析

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

而我们今天的问题是：是否可以将数组分割成两个子集，使得两个子集的元素和相等

其实这两个问题有共性，前者是求最多能装的价值，而后者是求是否存在一个子集和恰好等于sum/2。接下来，我们按照「0-1 背包」的思路进行分析

明确「状态」和「选择」

首先，我们先明确一下原问题是什么？「给定背包容量和可选物品，求能否恰好装满」，描述这样一个原问题需要给出两个条件，即：「背包的容量」和「可选择的物品」

而「状态」是原问题和子问题中会发生变化的变量，所以「状态」有两个，即：「背包的容量」和「可选择的物品」

再来确定「选择」，「选择」是导致「状态」产生变化的行为。这不就是对于每个可选择的物品，选择「装进背包」或者「不装进背包」嘛！！

明确dp数组的定义

由于「状态」有两个，所以需要一个二维的dp[][]数组。数组的下标就是状态转移中会变化的量，而数组的值就是子问题能否恰好装满

故：dp[i][j]的定义如下：对于前i个物品，当前背包容量j，这种情况下背包是否可以恰好装满 (true or false)

对于本问题，即：对于给定的集合中，若只对前i个数字进行选择，是否存在一个子集的和可以恰好凑出j

现在，我们也可以很快确定 base case。即：dp[0][...] = false; dp[...][0] = true，因为没有物品肯定不可以恰好凑出，而如果需要凑出的大小为 0，那么无论有多少物品肯定都是可以的

根据「选择」，思考状态转移的逻辑

注：这里的dp数组整体向后偏移了一位，即：dp[i][j]对应的是nums[i-1]

如果不把第i个元素加入集合，显然dp[i][j]应该等于dp[i-1][j]，继承之前的结果

如果把第i个元素加入集合，那么dp[i][j]应该等于dp[i-1][j-nums[i-1]]

如果选择了第i个元素，就要看背包的剩余重量j - nums[i-1]限制下是否能够被恰好装满

代码实现

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int i = 0; i < nums.length; i++) sum += nums[i];
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[][] dp = new boolean[nums.length + 1][target + 1];
    // base case
    for (int i = 0; i < dp.length; i++) dp[i][0] = true;

    for (int i = 1; i < dp.length; i++) {
        for (int j = 1; j < dp[0].length; j++) {
            if (j - nums[i - 1] < 0) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
        }
    }
    return dp[nums.length][target];
}

空间优化

dp 二维 -> 一维

先留个坑，以后再补！！！！

今天 (2022-09-25 22:45:23) 来补上这个坑！！

关于「二维 -> 一维」的优化可以先看 动态规划之最长回文子序列「dp 空间优化」

注：第二重循环需要反向遍历

如果正向遍历，新算出来的dp[j]会覆盖掉上一行的值，随着不断的向右，会用到左边的值，所以造成了上一行值的丢失

而如果反向遍历，随着不断的向左，一定不会用到右边的值，所以可以覆盖！！

具体如下图所示：

此时dp[j - nums[i - 1]]的值已经被覆盖了，所以正向遍历会出现问题！！

xxxxxxxxxx
public boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int i = 1; i <= nums.length; i++) {
        for (int j = target; j >= 1; j--) {
            if (j - nums[i - 1] >= 0) dp[j] = dp[j] || dp[j - nums[i - 1]];
        }
    }
    return dp[target];
}