0-1背包問題

（1）第一種情況：二維dp[i][j]數組

dp[i][j]表示[0,i]的物品放入容量為j背包的最大價值

不放物品i,dp[i][j]=dp[i-1][j]

放物品i,dp[i][j]=dp[i-1][j-w[i]]+v[i]

遞推公式為：

?dp[i][j]=dp[i-1][j];//不放

?if(w[i]<=j)dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);

? //當前物品體積小于j才可以放

兩層for循環，先遍歷物品或者先變量背包容量都可以

（2）第二種情況：一維dp[j]數組...相當于上一層數組拷貝下來，也叫滾動數組

dp[j]表示容量為j的背包所能放的最大價值

不放物品i,dp[j]=dp[j]

放物品i,dp[j]=dp[j-w[i]]+v[i]

遞推公式為：

dp[j]=max(dp[j],dp[j-w[i]]+v[i])

雙重for循環，必須先遍歷物品，再遍歷背包，同時背包要倒序遍歷。

for(int i=0;i<n;i++){

? ? ? ? for(int j=t;j>=nums[i];j--){

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

? ? ? ? }

? ? }

原因：保證每個物品只添加一次

416 分割等和子集

給你一個?只包含正整數?的?非空?數組?nums?。請你判斷是否可以將這個數組分割成兩個子集，使得兩個子集的元素和相等。

1 <= nums.length <= 200

1 <= nums[i] <= 100

示例 1：

輸入：nums = [1,5,11,5]
輸出：true
解釋：數組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

輸入：nums = [1,2,3,5]
輸出：false
解釋：數組不能分割成兩個元素和相等的子集。

• 背包的體積為sum / 2
• 背包要放入的商品（集合里的元素）重量為 元素的數值，價值也為元素的數值
• 背包如何正好裝滿，說明找到了總和為 sum / 2 的子集。
• 背包中每一個元素是不可重復放入。

0-1背包問題，相當于物品體積和價值都是nums[i]

對數組求和，sum為奇數一定不滿足

求出容量為sum/2時能放入的最大價值，如果剛好放慢，則說明可以分割為等和子集。

根據數組長度和大小，可以確定dp數組的大小，100*200/2=10000

int max(int a,int b){return a>b?a:b;
}
/*0-1背包問題，相當于物品體積和價值都是nums[i]
對數組求和，sum為奇數一定不滿足
求出容量為sum/2時能放入的最大價值，如果剛好放慢，則說明可以分割為等和子集
*/
bool canPartition(int* nums, int numsSize) {int sum=0,i,j;int dp[10005]={};//dp[j]表示背包體積為j能放入的最大體積for(i=0;i<numsSize;i++){sum+=nums[i];}if(sum%2!=0)return false;//數組和必為偶數else{for(i=0;i<numsSize;i++){//必須先遍歷物品for(j=sum/2;j>=nums[i];j--){//倒序遍歷，保證每個元素只添加一次dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);//放入物品i,dp[j-nums[i]]+nums[i}}}if(dp[sum/2]==sum/2)return true;else return false;
}

1049 最后一塊石頭的重量

有一堆石頭，用整數數組?stones?表示。其中?stones[i]?表示第?i?塊石頭的重量。

每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設石頭的重量分別為?x?和?y，且?x <= y。那么粉碎的可能結果如下：

• 如果?x == y，那么兩塊石頭都會被完全粉碎；
• 如果?x != y，那么重量為?x?的石頭將會完全粉碎，而重量為?y?的石頭新重量為?y-x。

最后，最多只會剩下一塊?石頭。返回此石頭?最小的可能重量?。如果沒有石頭剩下，就返回?0。

示例 1：

輸入：stones = [2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數組轉化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數組轉化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數組轉化為 [1,1,1]，
組合 1 和 1，得到 0，所以數組轉化為 [1]，這就是最優值。

示例 2：

輸入：stones = [31,26,33,21,40]
輸出：5

盡量把石頭分為重量相近的兩堆，保證相撞后重量最小

所以要盡可能分成重量為 sum / 2 的石頭堆,這樣剩下的石頭堆也是 盡可能接近 sum/2 的重量

轉化為背包問題，容量為sum/2時能裝入的最大重量

剩下重量為sum-dp[sum/2],sum/2向下取整，所以剩下的重量一定大于dp[sum/2]

最后返回剩下重量與dp[sum/2]的差即可

int max(int a,int b){return a>b?a:b;
}
/*
盡量把石頭分為重量相近的兩堆，保證相撞后重量最小
所以要盡可能分成重量為 sum / 2 的石頭堆,這樣剩下的石頭堆也是 盡可能接近 sum/2 的重量
轉化為背包問題，容量為sum/2時能裝入的最大重量
剩下重量為sum-dp[sum/2],sum/2向下取整，所以剩下的重量一定大于dp[sum/2]
最后返回剩下重量與dp[sum/2]的差即可
*/
int lastStoneWeightII(int* stones, int stonesSize) {int dp[15005]={};//dp[j]表示背包容量為j時所能放的最大價值int sum=0;for(int i=0;i<stonesSize;i++){sum+=stones[i];}int t=sum/2;for(int i=0;i<stonesSize;i++){for(int j=t;j>=stones[i];j--){dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);}}//sum向下取整，所以sum-dp[t]一定大于dp[t]return sum-dp[t]-dp[t];
}

總結：01背包問題，物品數量只有一個時，分為選和不選兩種情況討論

做題步驟

1、確定dp數組含義

2、確定遞推公式

3、初始化

4、遍歷。注意，二維dp數組遍歷無順序要求，一維dp數組必須先遍歷物品，再遍歷背包，并且背包要倒序遍歷。循環內j>w[i]