代碼隨想錄算法訓練營第四十四天 | 完全背包 、零錢兌換 II 、組合總和 Ⅳ

完全背包

題目鏈接：題目頁面 (kamacoder.com)

解釋一、01背包 一維 ：為什么要倒序遍歷背包？

首先要明白二維數組的遞推過程，然后才能看懂二維變一維的過程。

假設目前有背包容量為10，可以裝的最大價值， 記為g(10)。

即將進來的物品重量為6。價值為9。
那么此時可以選擇裝該物品或者不裝該物品。

如果不裝該物品，顯然背包容量無變化，這里對應二維數組，其實就是取該格子上方的格子復制下來，就是所說的滾動下來，直接g【10】 = g【10】，這兩個g【10】要搞清楚，右邊的g【10】是上一輪記錄的，也就是對應二維數組里上一層的值，而左邊是新的g【10】，也就是對應二維數組里下一層的值。

如果裝該物品，則背包容量= g(10-6) = g(4) + 9 ，也就是 g(10) = g(4) + 6 ,這里的6顯然就是新進來的物品的價值，g(10)就是新記錄的，對應二維數組里下一層的值，而這里的g(4)是對應二維數組里上一層的值，通俗的來講：你要找到上一層也就是上一狀態下 背包容量為4時的能裝的最大價值，用它來更新下一層的這一狀態，也就是加入了價值為9的物品的新狀態。

這時候如果是正序遍歷會怎么樣？ g(10) = g(4) + 6 ，這個式子里的g(4)就不再是上一層的了，因為你是正序啊，g(4) 比g(10)提前更新，那么此時程序已經沒法讀取到上一層的g(4)了，新更新的下一層的g(4)覆蓋掉了，這里也就是為啥有題解說一件物品被拿了兩次的原因。

解釋二、01背包到底先遍歷物品還是先遍歷背包呢？

其實在二維的時候，即使是先遍歷背包重量，再遍歷物品重量，你真的畫圖的時候會發現，永遠的數據來源，依舊還是max(不放，放）= max(正上方的值，左上角的值)。

那你在一維的時候，如果先遍歷背包容量的話:

如果你還是從左到右地遍歷背包容量：一樣會造成重復添加；

如果你從右到左地遍歷背包容量：相當于你的計算順序是先豎著寫完第四列，再豎著寫完第三列，再豎著寫完第二列。。。但你寫第四列的時候，第三列全部都是空的，左邊是沒有數據的，你永遠只在累加正上方的數。而如果你是先遍歷物品再遍歷背包，你的填空順序是，先寫第一行（從右往左寫），再寫第二行的時候，你的左邊是有數字的。。。

那你可能想問，我能不能做一個豎著的表格更新呢？其實沒有幫助的，你只要先一股腦地豎著算，你永遠沒法利用起左邊格子的數字——無法利用之前格子的數，那就不是動態規劃了

解釋三、為什么完全背包可以顛倒物品和背包的遍歷順序？

請想像一下 01背包的二維dp數組圖像 和 完全背包的二維dp數組圖像

01背包 的二維數組dp[i] [j]只取決于其左上角的值，所以 使用二維數組時可以從對物品和背包數組進行正序遍歷，且先物品還是先背包可以顛倒

01背包的一維數組dp[j] 因為

背包必須要倒序遍歷（參考上面解釋一、01背包 一維 ：為什么要倒序遍歷背包）

↓

如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品（解釋二）

↓

所以要先物品后背包

完全背包其dp[j]完全取決于

// 先遍歷物品再遍歷背包
import java.util.*;public class Main {public static void main (String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int V = sc.nextInt();int[] weights = new int[N];int[] values = new int[N];for(int i = 0; i < N; ++i) {weights[i] = sc.nextInt();values[i] = sc.nextInt();}int[] dp = new int[V + 1];for(int i = 0; i < N; ++i) {for(int j = weights[i]; j <= V; ++j) {dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}}System.out.println(dp[V]);}
}
// 先遍歷背包再遍歷物品
import java.util.*;public class Main {public static void main (String[] args) {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int V = sc.nextInt();int[] weights = new int[N];int[] values = new int[N];for(int i = 0; i < N; ++i) {weights[i] = sc.nextInt();values[i] = sc.nextInt();}int[] dp = new int[V + 1];for(int j = 1; j <= V; ++j) {for(int i = 0; i < N; ++i) {if(j >= weights[i]) {dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);}                }}System.out.println(dp[V]);}
}

零錢兌換 II

題目鏈接：518. 零錢兌換 II - 力扣（LeetCode）

這道題就是 494. 目標和 - 力扣（LeetCode）的完全背包版本

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。

如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

class Solution {public int change(int amount, int[] coins) {//  硬幣數量不限 -> 完全背包// dp[j] 表示：填滿j（包括j）這么大容積的包，有dp[j]種方法int[] dp = new int[amount + 1];// dp[0] = 1是 遞歸公式的基礎。如果dp[0] = 0 的話，后面所有推導出來的值都是0了。dp[0] = 1;// 因為純完全背包求得裝滿背包的最大價值是多少，和湊成總和的元素有沒有順序沒關系，即：有順序也行，沒有順序也行！// 而本題要求湊成總和的組合數，元素之間明確要求沒有順序/**以coins[0] = 1, coins[1] = 5， amount = 6為例先遍歷物品，就是先把1加入計算，然后再把5加入計算 -> 這樣得到的是 組合先遍歷背包，背包容量的每一個值，都是經過 1 和 5 的計算，包含了{1, 5} 和 {5, 1}兩種情況-> 這樣得到的是 排列 不理解的話可以打印dp數組來看看*/for(int i = 0; i < coins.length; ++i) {for(int j = coins[i]; j <= amount; ++j) {dp[j] += dp[j - coins[i]];}for(int ele : dp) {System.out.print(ele + ",");}System.out.println(" ");}return dp[amount];}
}  

組合總和 Ⅳ

題目鏈接：377. 組合總和 Ⅳ - 力扣（LeetCode）

本題與動態規劃：518.零錢兌換II (opens new window)就是一個鮮明的對比，一個是求排列，一個是求組合，遍歷順序完全不同

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.length; j++) {if (i >= nums[j]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
}