01背包理論基礎

面試掌握01背包，完全背包和重背包就夠用了。

背包問題的理論基礎重中之重是01背包，一定要理解透！

01 背包

有n件物品和一個最多能背重量為w 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。

每一件物品其實只有兩個狀態，取或者不取，所以可以使用回溯法搜索出所有的情況，那么時間復雜度就是o(2^n)，這里的n表示物品數量。

所以暴力的解法是指數級別的時間復雜度。進而才需要動態規劃的解法來進行優化！

舉例：背包最大重量為4。

物品為：

	重量	價值
物品0	1	15
物品1	3	20
物品2	4	30

問背包能背的物品最大價值是多少？

以下講解和圖示中出現的數字都是以這個例子為例。

二維數組01背包

依然動規五部曲分析一波。

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

對于背包問題，有一種寫法， 是使用二維數組，即dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。要時刻記著這個dp數組的含義，下面的一些步驟都圍繞這dp數組的含義進行的。

2. ?確定遞推公式

有兩個方向可以推出來dp[i][j]，

• 不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。(其實就是當物品i的重量大于背包j的重量或背包剩余重量小于i的重量時，物品i無法放進背包中，所以背包內的價值依然和前面相同。)
• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值。

所以dp[i][j]=?max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

3. dp數組如何初始化

關于初始化，一定要和dp數組的定義吻合，否則到遞推公式的時候就會越來越亂。

首先從dp[i][j]的定義出發，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價值總和一定為0。i是由i-1推出來的，所以i為0的時候就一定要初始化。剛才討論過j=0的情況，那么i=0時，dp[0][j]，即：存放編號0的物品時，各個容量的背包所能存放的最大價值。因此?j < weight[0]時，dp[0][j] 應該是 0，因為背包容量比編號0的物品重量還小。若j>=weight[0]，dp[0][j]的值為value[0]。

dp[0][j] 和 dp[i][0] 初始化以后，其他位置都會從i-1或者j-weight[i]而來，因此都會被不斷地覆蓋，所以初始化為0即可。

4. 確定遍歷順序

在如下圖中，可以看出，有兩個遍歷的維度：物品與背包重量，從哪個方向遍歷都可以，因此我們就從物品開始遍歷。

public static void backValue(int[]value, int[] weight, int bagWeight){int num=value.length;int[][]dp=new int[num][bagWeight+1];for(int j=weight[0];j<bagWeight;j++){dp[0][j]=value[0];}for(int i=1;i<num;i++){//從物品開始遍歷for(int j=1;j<=bagWeight;j++){if(j<weight[i]) dp[i][j]=dp[i-1][j];else{dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);}}}System.out.println(dp[num-1][bagWeight]);}   

一維數組01背包

上面的思路是用二維數組來解決01背包問題，還可以用滾動數組來解決，即把二維dp降維。

在使用二維數組的時候，遞推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其實可以發現如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

與其把dp[i - 1]這一層拷貝到dp[i]上，不如只用一個一維數組了，只用dp[j]（一維數組，也可以理解是一個滾動數組）。

因此，動規五部曲分析如下：

1. 確定dp數組的定義

在一維dp數組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。

2. 一維dp數組的遞推公式

dp[j]為 容量為j的背包所背的最大價值，那么如何推導dp[j]呢？

dp[j]可以通過dp[j - weight[i]]推導出來，dp[j - weight[i]]表示容量為j - weight[i]的背包所背的最大價值。

dp[j - weight[i]] + value[i] 表示 容量為 j - 物品i重量 的背包 加上 物品i的價值。（也就是容量為j的背包，放入物品i了之后的價值即：dp[j]）

此時dp[j]有兩個選擇，一個是取自己dp[j] 相當于 二維dp數組中的dp[i-1][j]，即不放物品i，一個是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，畢竟是求最大價值。

所以遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3. 一維dp數組如何初始化

dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]，那么dp[0]就應該是0，因為背包容量為0所背的物品的最大價值就是0。

那么dp數組除了下標0的位置，初始為0，其他下標應該初始化多少呢？

看一下遞歸公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp數組在推導的時候一定是取價值最大的數，如果題目給的價值都是正整數那么非0下標都初始化為0就可以了。

這樣才能讓dp數組在遞歸公式的過程中取的最大的價值，而不是被初始值覆蓋了。

那么我假設物品價值都是大于0的，所以dp數組初始化的時候，都初始為0就可以了。

4.?一維dp數組遍歷順序

二維dp遍歷的時候，背包容量是從小到大，而一維dp遍歷的時候，背包是從大到小。

因為倒序遍歷是為了保證物品i只被放入一次！。但如果一旦正序遍歷了，那么物品0就會被重復加入多次！

舉一個例子：物品0的重量weight[0] = 1，價值value[0] = 15

如果正序遍歷

dp[1] = dp[1 - weight[0]] + value[0] = 15

dp[2] = dp[2 - weight[0]] + value[0] = 30

此時dp[2]就已經是30了，意味著物品0，被放入了兩次，所以不能正序遍歷。

為什么倒序遍歷，就可以保證物品只放入一次呢？

倒序就是先算dp[2]

dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp數組已經都初始化為0）

dp[1] = dp[1 - weight[0]] + value[0] = 15

所以從后往前循環，每次取得狀態不會和之前取得狀態重合，這樣每種物品就只取一次了。

為什么二維dp數組遍歷的時候不用倒序呢？

因為對于二維dp，dp[i][j]都是通過上一層即dp[i - 1][j]計算而來，本層的dp[i][j]并不會被覆蓋！

先遍歷物品嵌套遍歷背包容量，那可不可以先遍歷背包容量嵌套遍歷物品呢？不可以！

因為一維dp的寫法，背包容量一定是要倒序遍歷（原因上面已經講了），如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品。

倒序遍歷的原因是，本質上還是一個對二維數組的遍歷，并且右下角的值依賴上一層左上角的值，因此需要保證左邊的值仍然是上一層的，從右向左覆蓋。

??一維和二維的區別：（1）一維到序遍歷，二維正序遍歷（2）一維只能先遍歷物品再遍歷背包，但是二維兩個順序都可。

public static void getBackValue(int[]value, int[] weight, int bagWeight){int num=value.length;int[]dp=new int[bagWeight+1];for(int j=weight[0];j<bagWeight;j++){dp[j]=value[0];}for(int i=1;i<num;i++){//從物品開始遍歷for(int j=bagWeight;j>=weight[i];j--){//要倒序遍歷dp[j]=Math.max(dp[j], dp[j-weight[i]]+value[i]);}}System.out.println(dp[bagWeight]);}   

416. 分割等和子集

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

注意: 每個數組中的元素不會超過 100 數組的大小不會超過 200

示例 1:

• 輸入: [1, 5, 11, 5]
• 輸出: true
• 解釋: 數組可以分割成 [1, 5, 5] 和 [11].

示例?2:

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

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

這道題希望能夠將一個數組拆成兩個子集a和b，使得a里面的元素和等于b里面的元素和。

沒有什么思路，直接看了代碼隨想錄。原來是01背包問題的變種。

01背包問題：有N件物品和一個最多能背重量為W 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。

注意題目描述中商品是不是可以重復放入。一個商品如果可以重復多次放入是完全背包，而只能放入一次是01背包。

要明確本題中我們要使用的是01背包，因為元素我們只能用一次。

回歸主題：首先，本題要求集合里能否出現總和為 sum / 2 的子集。（這一點是我沒有想到的）

那么來一一對應一下本題，看看背包問題如何來解決。

只有確定了如下四點，才能把01背包問題套到本題上來：

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

dp[j]表示：背包總容量是j，放進物品后，背包的最大價值為dp[j]。

那么如果背包需要滿足的容量為target，當dp[target]==target時，背包就裝滿了

class Solution {/**背包的可容納的重量為sum / 2背包要放入的商品（集合里的元素）重量為元素的數值，價值也為元素的數值背包如果正好裝滿，說明找到了總和為 sum / 2 的子集。背包中每一個元素是不可重復放入*/public boolean canPartition(int[] nums) {int sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2==1) return false;int target=sum/2;//weight[i]和value[i]都是nums[i]，當前的bacWeight為targetint[] dp=new int[target+1];for(int j=nums[0];j<target;j++){dp[j]=nums[0];}for(int i=1;i<nums.length;i++){ //先遍歷物品for(int j=target;j>=nums[i];j--){//重量要倒序遍歷dp[j]=Math.max(dp[j], dp[j-nums[i]]+nums[i]);}}if(dp[target]==target) return true;return false;}
}