LeetCode416. 分割等和子集

题目

分析

两个子集和相等，转化为找到所有元素总和一半的集合。注意不能回溯，因为时间复杂度为O（2^N）会超时。可以将此问题看成0-1背包问题。背包容量为sum / 2。如果总和一半为奇数，那么不可分成两个相同总和的子集。在此问题种物品的重量和价值为数字本身的数值。设dp[i][j]为从0-i中选取不超过容量j 的最大价值。动态转移方程就为01背包的转移方程。每个物品价值为正整数，所以dp数组初始化为0。若有负数，则应初始化为负无穷。

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto num:nums){
            sum += num;
        }
        if(sum % 2) return false;  //和为奇数必然不能分成两个和相同的子集
        sum /= 2;
        vector<vector<int>> dp(nums.size(),vector<int>(sum+1,0));
        //int dp[nums.size()][sum+1];
        //memset(dp,0,sizeof(dp));
        for(int j = 0;j <= sum;j++){  //初始化
            if(nums[0] <= j) dp[0][j] = nums[0];
        }
          
        for(int i = 1;i <nums.size();i++){
            for(int j = 0;j <= sum;j++){
                if( j < nums[i]) dp[i][j] = dp[i-1][j];
                else dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]] + nums[i]);
            }
        }
        if(sum == dp[nums.size()-1][sum]) return true;
        else return false;
    }
};

关于二维数组初始化可以memset,也可用vector，10—12行

优化

使用滚动数组将二维转换为一维。dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]] + nums[i])中上一层（i-1层）可以直接拷贝到 i 层上，这样就变成了dp[i][j] = max(dp[i][j],dp[i][j-nums[i]] + nums[i])，就可以把 第一维的 i 去掉，转为一维dp。dp[j]表示容量为j的背包可装的最大价值。动态转移方程：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。

一维dp需要注意几个问题：

1.遍历顺序：遵从先背包后容量。并且容量要逆序遍历。

解释：不可先容量后背包，先容量后背包这样背包中就只有一个物品。逆序遍历保证每个物品放入一次。

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto num:nums){
            sum += num;
        }
        if(sum % 2) return false;  //和为奇数必然不能分成两个和相同的子集
        sum /= 2;
        vector<int>dp(sum+1,0);
          
        for(int i = 1;i <nums.size();i++){
            for(int j = sum;j >= nums[i];j--){  //逆序
                dp[j] = max(dp[j],dp[j-nums[i]] + nums[i]);
            }
        }
        if(sum == dp[sum]) return true;
        else return false;
    }
};