LeetCode

背包問題

01背包

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

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

暴力的解法是指數(shù)級(jí)別的時(shí)間復(fù)雜度。進(jìn)而才需要?jiǎng)討B(tài)規(guī)劃的解法來進(jìn)行優(yōu)化。

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

	重量	價(jià)值
物品0	1	15
物品1	3	20
物品2	4	30

問背包能背的物品最大價(jià)值是多少？

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

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

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

   • 不放物品 i ：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]。(其實(shí)就是當(dāng)物品i的重量大于背包j的重量時(shí)，物品i無法放進(jìn)背包中，所以背包內(nèi)的價(jià)值依然和前面相同。)
   • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價(jià)值），就是背包放物品i得到的最大價(jià)值
     所以遞推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. 初始化

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

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

   dp[0][j]，即：i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。

   當(dāng) j < weight[0]的時(shí)候，dp[0][j] 應(yīng)該是 0，因?yàn)楸嘲萘勘染幪?hào)0的物品重量還小。

   當(dāng)j >= weight[0]時(shí)，dp[0][j] 應(yīng)該是value[0]，因?yàn)楸嘲萘糠抛銐蚍啪幪?hào)0物品。

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

4. 遍歷順序

   兩個(gè)遍歷維度： 物品與背包重量

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

   

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

   
   

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);}/*** 動(dòng)態(tài)規(guī)劃獲得結(jié)果* @param weight  物品的重量* @param value   物品的價(jià)值* @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ù)組后，其中默認(rèn)的值就是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]) {/*** 當(dāng)前背包的容量都沒有當(dāng)前物品i大的時(shí)候，是不放物品i的* 那么前i-1個(gè)物品能放下的最大價(jià)值就是當(dāng)前情況的最大價(jià)值*/dp[i][j] = dp[i-1][j];} else {/*** 當(dāng)前背包的容量可以放下物品i* 那么此時(shí)分兩種情況：*    1、不放物品i*    2、放物品i* 比較這兩種情況下，哪種背包中物品的最大價(jià)值最大*/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ù)組（滾動(dòng)數(shù)組）

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

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

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

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

---

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

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

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

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

從后往前循環(huán)，每次取得狀態(tài)不會(huì)和之前取得狀態(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時(shí)，能獲得的最大價(jià)值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] + " ");}

分割等和子集

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

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

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

dp[j]表示 背包總?cè)萘?#xff08;所能裝的總重量）是j，放進(jìn)物品后，背的最大重量為dp[j]。

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

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

如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層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;}   
}