01背包

求集合里是否出現總和為sum/2的子集。

背包體積為sum/2

背包放入的商品的重量為元素的數值，價值也為元素的數值

背包如何正好被裝滿，說明找到了總和為sum/2的子集

背包中每個元素都是不可重復放入的。

1、確定dp數組以及下標含義

dp[j]表示容量為j的背包，所背物品價值可以最大為dp[j]。

dp[j]表示背包總容量為j，最大可以湊成j的子集總和為dp[j]。

2、確定遞推公式

dp[j] = max(dp[j],dp[j-nums[i]] + nums[i]);

3、初始化

vector<int> dp(target+1,0);	//target為背包容量

4、確定遍歷順序

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]);}
}

AC代碼：

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(int num : nums){sum += num;}if(sum % 2 != 0) return false;int target = sum / 2;vector<int> dp(target+1,0);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]);if(dp[j] == target) return true;}}if(dp[target] == target) return true;else return false;}
};

將石頭盡量分成兩堆相同重量，然后相撞。分成兩堆的思路與上一題一致。

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for(int stone : stones){sum += stone;}int target = sum / 2;//dp[target]，容量為target的背包最多能背多重的石頭vector<int> dp(target+1,0);for(int i = 0; i < stones.size(); i++){for(int j = target; j >= stones[i]; j--){dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);}}return sum - dp[target]*2;}
};

所有數字可以分為兩堆，一堆符號為正，一堆符號為負。
pos + neg = S 且 pos - neg = sum
所以pos = (S+sum)/2,問題轉化為集合nums中找出和為pos的組合。
此時問題就轉化為，裝滿容量為pos背包，有幾種方法。
這次和之前遇到的背包問題不一樣了，之前都是求容量為j的背包，最多能裝多少。
本題則是裝滿有幾種方法。其實這就是一個組合問題了。
1、確定dp數組以及下標
dp[j]表示，填滿體積為j的背包，有dp[j]種方法。

2、確定遞推公式
不考慮nums[i],填滿容量為j-nums[i]的背包，有dp[j-nums[i]]種方法，
如果能搞到nums[i],則填滿容量為j-nums[i]的背包，就有dp[j]+dp[j-nums[i]]種方法。

dp[j] += dp[j-nums[i]]

3、初始化dp數組
dp[0] = 1，裝滿容量為0的背包，有1種方法。其他dp[i]均設置為0，在不知道nums[i]的情況下，沒有方法。

4、確定遍歷順序
nums外循環，j內循環倒序。

AC代碼：

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int num : nums)sum += num;//如果絕對值和比targetabs小，說明都用同一個符號也不能湊成if(sum < abs(target)) return 0;//如果不能完整的分成兩組，那么說明沒有方法if((target + sum) % 2 == 1) return 0;int bagWeight = (target + sum)/2;vector<int> dp(bagWeight+1,0);dp[0] = 1;for(int i = 0; i < nums.size(); i++){for(int j = bagWeight; j >= nums[i]; j--){dp[j] += dp[j-nums[i]];}}return dp[bagWeight];}
};