背包問題

1. 01背包指的是物品只有1個(gè)，可以選也可以不選。
2. 完全背包是物品有無數(shù)個(gè)，可以選幾個(gè)也可以不選。

二維數(shù)組01背包

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

輸入: 
weight: [1,3,4],value: [15,20,30],背包體積: 4
輸出：35

解題思路

1. dp數(shù)組，從下標(biāo)[0-i]的物品里面任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
2. 不放物品i，物品i由于體積問題放不進(jìn)去，dp[i][j]=dp[i-1][j]
3. 放物品i，dp[i][j]=dp[i-1][j-weight[i]]+value[i]

Java實(shí)現(xiàn)

public class BagProblem {public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagSize = 4;System.out.println(new BagProblem().testWeightBagProblem(weight, value, bagSize));}public int testWeightBagProblem(int[] weight, int[] value, int bagSize) {int size = weight.length;//0-size-1個(gè)物品放入到大小為bagSize的背包中int[][] dp = new int[size][bagSize + 1];//當(dāng)bagSize=0時(shí)，dp[i][0]=0//當(dāng)只有索引為0的物品可以選擇，且放的下(j<=bagSize)，dp[0][j]的值等于放入索引為0的價(jià)值for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}for (int i = 1; i < size; 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 {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}}for (int i = 0; i < size; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println("\n");}return dp[size - 1][bagSize];}
}

一維數(shù)組01背包

解題思路

1. dp[j]表示：容量為j的背包，所背的物品價(jià)值可以最大為dp[j]。
2. 遞推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3. 遍歷詳解：當(dāng)i=0，初始化dp[j]，只有j>weight[i]的時(shí)候，會(huì)被初始化。當(dāng)i=1的時(shí)候，可以選擇的商品有[0,1]，dp[j]是在原有的dp數(shù)組上判斷的，只有當(dāng)可以存放下索引為1的商品，且dp[j - weight[i]] + value[i]>dp[j]，該數(shù)值才會(huì)被更新。
4. 選擇逆序背包容量，主要是dp[j]和dp[j-weight[i]]的初始化順序的問題。在二維數(shù)組中，比較的是dp[i-1][j-weight[i]]，是第i-1層的dp[j-weight[i]]

Java實(shí)現(xiàn)

public class BagProblem_II {public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;System.out.println(new BagProblem_II().testWeightBagProblem(weight, value, bagWight));}private int 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]);System.out.println(dp[j] + "," + j + "," + i);}}//打印dp數(shù)組for (int j = 0; j <= bagWeight; j++) {System.out.print(dp[j] + " ");}System.out.println();return dp[bagWeight];}
}

416. 分割等和子集

力扣題目鏈接

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

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

解題思路

1. 集合里能否出現(xiàn)總和為 sum / 2 的子集
2. dp[j]：最大值為j的子集
3. 如果第i個(gè)元素沒有放到集合中，值是dp[i-1][j]；如果第i個(gè)元素放進(jìn)集合中，值是dp[i-1][j-num[i]]+num[i]。

dp[i][j]= dp[i?1][j]，當(dāng)i-1的數(shù)組已經(jīng)滿足了等于j的條件
dp[i][j]= true, 當(dāng)nums[i] = j滿足。
dp[i?1][j?nums[i]].當(dāng)nums[i] < j。
dp[i][j]為true的三個(gè)條件，只需要滿足一個(gè)即可。

Java實(shí)現(xiàn)

    public boolean canPartition(int[] nums) {if (nums == null || nums.length == 0) return false;int len = nums.length;int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < len; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] == target;}

1049.最后一塊石頭的重量II

力扣題目鏈接

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

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

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

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

輸入：stones = [2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。

解題思路

1. dp[target]里是容量為target的背包所能背的最大重量。分成兩堆石頭，一堆石頭的總重量是dp[target]，另一堆就是sum - dp[target]。相撞之后剩下的最小石頭重量就是 (sum - dp[target]) - dp[target]。

Java實(shí)現(xiàn)

class Solution_LC1049 {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp數(shù)組int[] dp = new int[target + 1];for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//兩種情況，要么放，要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}

494.目標(biāo)和

力扣題目鏈接

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 。

向數(shù)組中的每個(gè)整數(shù)前添加 '+' 或 '-' ，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè) 表達(dá)式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串聯(lián)起來得到表達(dá)式 "+2-1" 。

返回可以通過上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目。

輸入：nums = [1,1,1,1,1], target = 3
輸出：5
解釋：一共有 5 種方法讓最終目標(biāo)和為 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

解題思路

1. 數(shù)組集合可以分為正數(shù)集合和負(fù)數(shù)集合，正+負(fù)=sum，正-負(fù)=target，題目可以轉(zhuǎn)化為求sum=正數(shù)的子集合的個(gè)數(shù)。
2. 純01背包問題：裝滿背包最大的價(jià)值是多少；分割等和子集，能不能裝滿這個(gè)背包；最后一塊石頭的重量，給定背包，能裝多少裝多少；目標(biāo)和：裝滿這個(gè)背包有多少方法？
3. dp數(shù)組的含義：填滿j（包括j）這么大容積的包，有dp[j]種方法。
4. dp[j]=dp[j-nums[i]]的累加。比如nums[i]=2，dp[5]+=dp[5-nums[i]]。

Java實(shí)現(xiàn)

class Solution_LC494 {public int findTargetSumWays(int[] nums, int target) {int len = nums.length;int sum = 0;for (int i = 0; i < len; i++) {sum += nums[i];}if (target > sum || target < -sum) {return 0;}if ((target + sum) % 2 != 0) {return 0;}int goal = (target + sum) / 2;//填滿j（包括j）這么大容積的包，有dp[j]種方法int[] dp = new int[goal + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = goal; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[goal];}
}

二維數(shù)組的實(shí)現(xiàn)

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}int diff = sum - target;if (diff < 0 || diff % 2 != 0) {return 0;}int n = nums.length, neg = diff / 2;int[][] dp = new int[n + 1][neg + 1];dp[0][0] = 1;for (int i = 1; i <= n; i++) {int num = nums[i - 1];for (int j = 0; j <= neg; j++) {dp[i][j] = dp[i - 1][j];if (j >= num) {dp[i][j] += dp[i - 1][j - num];}}}return dp[n][neg];}
}

474.一和零

力扣題目鏈接

給你一個(gè)二進(jìn)制字符串?dāng)?shù)組 strs 和兩個(gè)整數(shù) m 和 n 。

請(qǐng)你找出并返回 strs 的最大子集的長度，該子集中 最多 有 m 個(gè) 0 和 n 個(gè) 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

輸入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
輸出：4
解釋：最多有 5 個(gè) 0 和 3 個(gè) 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他滿足題意但較小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不滿足題意，因?yàn)樗?4 個(gè) 1 ，大于 n 的值 3 。

解題思路

1. dp[i][j]表示i個(gè)0和j個(gè)1時(shí)的最大子集

Java實(shí)現(xiàn)

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m + 1][n + 1];for (String str : strs) {int zeroNum = 0;int oneNum = 0;for (int i = 0; i < str.length(); i++) {if (str.charAt(i) == '0') {zeroNum++;} else {oneNum++;}}for (int i = m; i >= zeroNum; i--) {for (int j = n; j >= oneNum; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);}}}return dp[m][n];}
}

總結(jié)一下

純 0 - 1 背包 是求 給定背包容量 裝滿背包 的最大價(jià)值是多少。
416. 分割等和子集 是求 給定背包容量，能不能裝滿這個(gè)背包。
1049. 最后一塊石頭的重量 II 是求 給定背包容量，盡可能裝，最多能裝多少
494. 目標(biāo)和 是求 給定背包容量，裝滿背包有多少種方法。
本題是求 給定背包容量，裝滿背包最多有多少個(gè)物品。