😄416.分割等和子集

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

示例

示例 1：

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

输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200 1 <= nums[i] <= 100

思路

基本思想

既然要分割成两个子集，并且两个子集的和要相等，那么就先求出这个和sum是多少，直接将所有元素累加起来除以2即可

由于元素都是正整数，所以分成子集之后的和也是正整数，所以求出的和如果不是正整数那么肯定无法分割，只有是正整数才有可能可以分割

求出的sum当成背包的容量，集合中的元素当成物品，一旦有元素组合起来可以刚好把背包填满，就说明可以分割，因为背包的容量是评分的，所以剩下的元素组合起来肯定也可以将背包填满

现在要解决的问题就是如何判断元素的组合将背包刚好填满

什么叫刚好装满：容量为sum，装了sum，也就是dp[sum]=sum，也就是说要求的dp[sum]，求完之后判断dp[sum]==sum？即可

执行流程

1. 确定sum的值，如果sum不是正整数，直接返回false

2. sum是正整数，就让背包的容量为sum，此时正常执行01背包问题的流程

   要的是dp[sum]，但是dp数组中其他的元素也得求出来，因为dp[sum]是由dp数组前面的值推导得到的

   • 初始化dp数组为0

   • 从前向后依次向背包中装填元素

   • 背包容量从大到小防止元素重复装入

   • 确定递推方程，本题中元素的值既是权值也是价值 $$ dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]) $$ 重点是不放当前元素的时候，形成的价值是dp[j]，而不是dp[j-1]，因为dp[j]的含义是：容量为j的背包，所背的物品价值可以最大为dp[j]。

   • 遍历完成判断dp[sum]==sum

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int temp=accumulate(nums.begin(),nums.end(),0);
        if(temp%2==1){//奇数除以2不是正整数，无法分割，直接返回false
            return false;
        }
        int sum=temp/2;
        //初始化dp数组
        vector<int> dp(sum+1,0);
        //开始动态规划
        for(int i=0;i<nums.size();++i){
            //只有能装下才有意义
            for(int j=sum;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        //遍历结束看看是不是刚好装满
        return dp[sum]==sum;
    }
};

总结

主要是求的背包的容量，最后判断背包刚好被装满就说明可以分割，知道这两点其余的步骤就是0-1背包的步骤

注意0-1背包中当前元素不放进去形成的价值为dp[j]而不是dp[j-1]，因为j代表的是背包的容量，不像是二维dp[i-1][j],i-1代表上一个物品，要明白这一点