leetcode|LeetCode第 416 题（分割等和子集(C++)） leetcode|动态规划

416. 分割等和子集 - 力扣（LeetCode）
这是典型的子集背包问题：经典动态规划：子集背包问题 - labuladong的算法小抄
可以转化为0-1背包问题：
具体看注释

/* 转化为背包问题：给定?个容量为 sum / 2 的背包和 N 个物品，每个物品的重量nums[i] 。现在让你装物品，求问是否存在?种装法，恰好可以装满背包 */ class Solution { public: bool canPartition(vector& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); //计算总和 if(sum % 2) return false; //和为奇数时不可能划分为两个和相等的子集 sum /= 2; int n = nums.size(); //dp[i][j]表示，对于前i个物品，当前背包容量为j时，如果dp[i][j] = 1,则说明可以刚好将背包装满 //也就是从数组的 [0, i] 这个子区间内挑选一些正整数，他们的和恰好为j vector> dp(n+1, vector(sum+1)); for(int i = 0; i <= n; ++i) dp[i][0] = 1; //容量为0的时候（第一列）//对于物品的选择：可选（此时可以选可以不选），不可选（该物品重量大于剩余容量） for(int i = 1; i <= n; ++i){ for(int j = 1; j <= sum; ++j){ //背包容量不足，无法装下第i个物品 if(nums[i-1] > j)dp[i][j] = dp[i-1][j]; //装入背包或者不装入背包 //什么时候dp[i][j] == 1呢？也就是前i个物品刚好可以装满j的重量，对应当前物品选或不选有两种情况： //1、如果dp[i-1][j] == 1（前i-1个物品，恰好可以装满j的容量），那么此时不选择当前物品i的话 //dp[i][j] = dp[i-1][j] = 1,也就是前i个物品也可以刚好装满j的容量 //2、如果前i-1个物品，刚好可以装满j - nums[i-1]的容量，那么把当前物品装进去，就刚好能装满j的重量 //此时dp[i][j] = dp[i-1][j - nums[i-1]] = 1 //其他情况是dp[i][j] = 0,前i个物品没法做到刚好装满j的容量 elsedp[i][j] = dp[i-1][j - nums[i-1]] || dp[i-1][j]; } } return dp[n][sum]; } };

【leetcode|LeetCode第 416 题（分割等和子集(C++)）】状态压缩：

/* 转化为背包问题：给定?个容量为 sum / 2 的背包和 N 个物品，每个物品的重量nums[i] 。现在让你装物品，求问是否存在?种装法，恰好可以装满背包 */ class Solution { public: bool canPartition(vector& nums) { int sum = accumulate(nums.begin(), nums.end(), 0); //计算总和 if(sum % 2) return false; //和为奇数时不可能划分为两个和相等的子集 sum /= 2; int n = nums.size(); vector dp(sum+1, 0); dp[0] = 1; //容量为0的时候（第一列）//对于物品的选择：可选（此时可以选可以不选），不可选（该物品重量大于剩余容量） for(int i = 1; i <= n; ++i){ for(int j = sum; j >= 1; --j){ if(nums[i-1] > j)dp[j] = dp[j]; elsedp[j] = dp[j - nums[i-1]] || dp[j]; } } return dp[sum]; } };