动态规划：11分割等和子集

动态规划：11分割等和子集

416. 分割等和子集

这道题目初步看，和如下两题几乎是一样的，大家可以用回溯法，解决如下两题

• 698.划分为k个相等的子集
• 473.火柴拼正方形

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。

本题是可以用回溯暴力搜索出所有答案的，但最后超时了，也不想再优化了，放弃回溯，直接上01背包吧。

如果对01背包不够了解，建议仔细看完如下两篇：

• 动态规划：09 0-1背包理论基础I
• 动态规划：10 0-1背包理论基础II（滚动数组）

01背包

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

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。

要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题，看看背包问题如何来解决。

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

以上分析完，我们就可以套用01背包，来解决这个问题了。

五部曲

1. 确定dp数组含义：dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。

   本题中每一个元素的数值既是重量，也是价值。

   套到本题，dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。

   那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

   大家可能想，那还有装不满的时候？

   拿输入数组 [1, 5, 11, 5]，举例， dp[7] 只能等于 6，因为 只能放进 1 和 5。

   而dp[6] 就可以等于6了，放进1 和 5，那么dp[6] == 6，说明背包装满了。

   我们只需要判断dp[j]的最大值是否等于j，就可以判断是否装满

2. 确定递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

   本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

   所以递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);

3. dp数组初始化：dp[j] = 0

   在01背包，一维dp如何初始化，已经讲过，

   从dp[j]的定义来看，首先dp[0]一定是0。

   如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

   这样才能让dp数组在递推的过程中取得最大的价值，而不是被初始值覆盖了。

   本题题目中 只包含正整数的非空数组，所以非0下标的元素初始化为0就可以了。

4. 遍历顺序：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

   // 开始 01背包
   for(int i = 0; i < nums.size(); i++) {
       for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
           dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
       }
   }
   1
   2
   3
   4
   5
   6

5. debug：打印dp数组

代码

class Solution {
    public boolean canPartition(int[] nums) {
        //题目写了数组非空
        int len = nums.length;
        int sum = 0;
        for(int num : nums) sum += num;
        //如果是奇数则没有意义,不能平分
        if((sum % 2) != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        //初始化全是0：dp[0] = 0,其他的需要初始化非负最小整数，不能让初始化数字覆盖掉我们计算的值
        for(int i = 0; i < len; i++) {
            //物品 i 的重量是 nums[i]，其价值也是 nums[i]
            for(int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], (dp[j - nums[i]] + nums[i]));
            }

            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 17ms）

            if(dp[target] == target) return true;
        }

        return dp[target] == target;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)，虽然dp数组大小为一个常数，但是大常数

总结

这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。

看代码的话，就可以发现，基本就是按照01背包的写法来的。