LeetCode

背包問題

01背包

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

暴力的解法： 回溯，時間復雜度就是$o(2^n)$，這里的n表示物品數(shù)量。

暴力的解法是指數(shù)級別的時間復雜度。進而才需要動態(tài)規(guī)劃的解法來進行優(yōu)化。

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

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

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

二維dp數(shù)組01背包

1. dp數(shù)組：dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。

2. 遞推公式：兩個方向推出來dp[i][j]

   • 不放物品 i ：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。(其實就是當物品i的重量大于背包j的重量時，物品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. 初始化

   如果背包容量 j 為 0 的話，dp[i][0]， 無論選取哪些物品，背包價值總和一定為0。

   狀態(tài)轉移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推導出來，那么i為0的時候就一定要初始化。

   dp[0][j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價值。

   當 j < weight[0]的時候，dp[0][j] 應該是 0，因為背包容量比編號0的物品重量還小。

   當j >= weight[0]時，dp[0][j] 應該是value[0]，因為背包容量放足夠放編號0物品。

for (int j = 0 ; j < weight[0]; j++) {  // 當然這一步，如果把dp數(shù)組預先初始化為0了，這一步就可以省略，但很多同學應該沒有想清楚這一點。dp[0][j] = 0;
}
// 正序遍歷
for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];
}

4. 遍歷順序

   兩個遍歷維度： 物品與背包重量

   先遍歷物品，再遍歷背包的過程如圖所示：

   

   先遍歷背包，再遍歷物品呢，如圖：

   
   

public class BagProblem {public static void main(String[] args) {int[] weight = {1,3,4};int[] value = {15,20,30};int bagSize = 4;testWeightBagProblem(weight,value,bagSize);}/*** 動態(tài)規(guī)劃獲得結果* @param weight  物品的重量* @param value   物品的價值* @param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 創(chuàng)建dp數(shù)組int goods = weight.length;  // 獲取物品的數(shù)量int[][] dp = new int[goods][bagSize + 1];// 初始化dp數(shù)組// 創(chuàng)建數(shù)組后，其中默認的值就是0for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}// 填充dp數(shù)組for (int i = 1; i < weight.length; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) {/*** 當前背包的容量都沒有當前物品i大的時候，是不放物品i的* 那么前i-1個物品能放下的最大價值就是當前情況的最大價值*/dp[i][j] = dp[i-1][j];} else {/*** 當前背包的容量可以放下物品i* 那么此時分兩種情況：*    1、不放物品i*    2、放物品i* 比較這兩種情況下，哪種背包中物品的最大價值最大*/dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);}}}// 打印dp數(shù)組for (int i = 0; i < goods; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println("\n");}}
}

一維 dp 數(shù)組（滾動數(shù)組）

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

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

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

這就是滾動數(shù)組的由來，需要滿足的條件是上一層可以重復利用，直接拷貝到當前層。

---

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

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

dp數(shù)組初始化的時候，都初始為0就可以了。

注意： 遍歷背包的順序是倒序遍歷，保證物品只放入一次。

從后往前循環(huán)，每次取得狀態(tài)不會和之前取得狀態(tài)重合，這樣每種物品就只取一次了。

public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;testWeightBagProblem(weight, value, bagWight);
}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen = weight.length;//定義dp數(shù)組：dp[j]表示背包容量為j時，能獲得的最大價值int[] dp = new int[bagWeight + 1];//遍歷順序：先遍歷物品，再遍歷背包容量for (int i = 0; i < wLen; i++){for (int j = bagWeight; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}//打印dp數(shù)組for (int j = 0; j <= bagWeight; j++){System.out.print(dp[j] + " ");}

分割等和子集

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

本題要求集合里能否出現(xiàn)總和為 sum / 2 的子集。

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

dp[j]表示 背包總容量（所能裝的總重量）是j，放進物品后，背的最大重量為dp[j]。

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

dp[0]一定是0。如果題目給的價值都是正整數(shù)那么非0下標都初始化為0就可以了，如果題目給的價值有負數(shù)，那么非0下標就要初始化為負無窮。這樣才能讓dp數(shù)組在遞推的過程中取得最大的價值，而不是被初始值覆蓋了。

如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內層，且內層for循環(huán)倒序遍歷！

class Solution {public boolean canPartition(int[] nums) {if(nums == null || nums.length == 0) return false;int n = nums.length;int sum = 0;for (int num : nums) {sum += num;}if (sum % 2 != 0) return false;int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < n; 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 dp[target] == target;}   
}