分割等和子集
一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。
本题中使用的是01背包，因为元素我们只能用一次。
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
动态背包（二维背包）
dp[ i ][ j ] 中
- i 是放入背包中元素的范围，从0 - i 中取元素，每个元素取一次。
- j 是当前背包的容量上限
本题的核心是找到刚好背包容量是sum/2装满的时候。
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0 , target = 0; for(auto it:nums) sum += it; //如果和是奇数，就不能分成两个相等的子集 if(sum%2 == 1) return false; //目标是找到sum/2 target = sum/2; vector<vector<int>> dp(nums.size() , vector<int>(target+1 , 0)); //背包初始化第一行的值，第一行是只能放第一个元素 //检查背包的大小能否放进去，能就放进去第一个元素，不能就空着 //第一列是背包容量是0的时候，dp[i][0]也都是0，不用额外初始化 for(int j = 1 ; j<=target ;j++ ) if(j>=nums[0]) dp[0][j] = nums[0]; //开始遍历 for(int i=1 ; i<nums.size() ;i++) { for(int j = 1 ; j<=target ;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]); } } //最后在背包大小是sum/2的一列里找，刚好背包装满的 for(int i=0; i<nums.size();i++) if(dp[i][target]==target) return true; return false; } };
动态背包+滚动数组（一维背包）
dp[ j ]表示 背包总容量是 j
dp[ j ] = max(dp[ j ], dp[ j - nums[ i ] ] + nums[ i ])
相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0 , target = 0; for(auto it:nums) sum += it; if(sum%2 == 1) return false; target = sum/2; vector<int> dp(target+1,0); //开始遍历 for(int i=0 ; i<nums.size() ;i++) { //倒叙背包容量，防止一个值被多次存入 for(int j=target ; j >= 0 ; j-- ) { //如果当前背包容量可以放入该值 //就找放进去和不放进去大的一个 if(j>=nums[i]) dp[j] = max( dp[j] , dp[j-nums[i]] + nums[i]); //如果放不进去，就不变 else dp[j] = dp[j]; } } //当背包容量是sum/2的时候刚好装满，就认为成功 if(dp[target] == target) return true; else return false; } };
二刷(二维)
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for(auto it:nums) sum += it; if(sum%2 == 1) return false; vector<vector<int>> dp(nums.size() , vector<int>(sum/2+1,0)); for(int j=0 ; j<sum/2 ;j++) if(j >= nums[0]) dp[0][j] = nums[0]; for(int i=1 ; i<nums.size() ;i++ ) { for(int j=1 ; j<=sum/2 ; 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] ); } } for(int i=0 ; i<nums.size();i++) if(dp[i][sum/2] == sum/2) return true; return false; } };
二刷(一维)
class Solution { public: bool canPartition(vector<int>& nums) { int sum = 0; for(auto it:nums) sum += it; if(sum%2 == 1) return false; vector<int> dp(sum/2+1,0); for(int i=0 ; i<nums.size() ;i++ ) { for(int j=sum/2 ; j>=nums[i]; j--) { dp[j] = max(dp[j] , dp[j-nums[i]] + nums[i]); } } if(dp[sum/2] == sum/2) return true; return false; } };
