当前位置:网站首页>經典動態規劃:完全揹包問題

經典動態規劃:完全揹包問題

2020-11-06 01:18:03 itread01

讀完本文,你可以去力扣拿下如下題目: [518.零錢兌換II](https://leetcode-cn.com/problems/coin-change-2) **-----------** 零錢兌換 2 是另一種典型揹包問題的變體,我們前文已經講了 [經典動態規劃:0-1 揹包問題](https://labuladong.gitbook.io/algo)。 **希望你已經看過前兩篇文章**,看過了動態規劃和揹包問題的套路,這篇繼續按照揹包問題的套路,列舉一個揹包問題的變形。 本文聊的是 LeetCode 第 518 題 Coin Change 2,題目如下: ![title](https://gitee.com/labuladong/pictures/raw/master/knapsackCoin/title.jpg) ```java int change(int amount, int[] coins); ``` PS:至於 Coin Change 1,在我們前文 [動態規劃套路詳解](https://labuladong.gitbook.io/algo) 寫過。 **我們可以把這個問題轉化為揹包問題的描述形式**: 有一個揹包,最大容量為 `amount`,有一系列物品 `coins`,每個物品的重量為 `coins[i]`,**每個物品的數量無限**。請問有多少種方法,能夠把揹包恰好裝滿? 這個問題和我們前面講過的兩個揹包問題,有一個最大的區別就是,每個物品的數量是無限的,這也就是傳說中的「**完全揹包問題**」,沒啥高大上的,無非就是狀態轉移方程有一點變化而已。 下面就以揹包問題的描述形式,繼續按照流程來分析。 PS:**我認真寫了 100 多篇原創,手把手刷 200 道力扣題目,全部發布在 [labuladong的演算法小抄](https://links.jianshu.com/go?to=https%3A%2F%2Flabuladong.gitbook.io%2Falgo%2F),持續更新**。建議收藏,**按照我的文章順序刷題**,掌握各種演算法套路後投再入題海就如魚得水了。 ### 解題思路 **第一步要明確兩點,「狀態」和「選擇」**。 狀態有兩個,就是「揹包的容量」和「可選擇的物品」,選擇就是「裝進揹包」或者「不裝進揹包」嘛,揹包問題的套路都是這樣。 明白了狀態和選擇,動態規劃問題基本上就解決了,只要往這個框架套就完事兒了: ```python for 狀態1 in 狀態1的所有取值: for 狀態2 in 狀態2的所有取值: for ... dp[狀態1][狀態2][...] = 計算(選擇1,選擇2...) ``` **第二步要明確 `dp` 陣列的定義**。 首先看看剛才找到的「狀態」,有兩個,也就是說我們需要一個二維 `dp` 陣列。 `dp[i][j]` 的定義如下: 若只使用前 `i` 個物品,當揹包容量為 `j` 時,有 `dp[i][j]` 種方法可以裝滿揹包。 換句話說,翻譯回我們題目的意思就是: **若只使用 `coins` 中的前 `i` 個硬幣的面值,若想湊出金額 `j`,有 `dp[i][j]` 種湊法**。 經過以上的定義,可以得到: base case 為 `dp[0][..] = 0, dp[..][0] = 1`。因為如果不使用任何硬幣面值,就無法湊出任何金額;如果湊出的目標金額為 0,那麼“無為而治”就是唯一的一種湊法。 我們最終想得到的答案就是 `dp[N][amount]`,其中 `N` 為 `coins` 陣列的大小。 大致的偽碼思路如下: ```python int dp[N+1][amount+1] dp[0][..] = 0 dp[..][0] = 1 for i in [1..N]: for j in [1..amount]: 把物品 i 裝進揹包, 不把物品 i 裝進揹包 return dp[N][amount] ``` **第三步,根據「選擇」,思考狀態轉移的邏輯**。 注意,我們這個問題的特殊點在於物品的數量是無限的,所以這裡和之前寫的揹包問題文章有所不同。 **如果你不把這第 `i` 個物品裝入揹包**,也就是說你不使用 `coins[i]` 這個面值的硬幣,那麼湊出面額 `j` 的方法數 `dp[i][j]` 應該等於 `dp[i-1][j]`,繼承之前的結果。 **如果你把這第 `i` 個物品裝入了揹包**,也就是說你使用 `coins[i]` 這個面值的硬幣,那麼 `dp[i][j]` 應該等於 `dp[i][j-coins[i-1]]`。 首先由於 `i` 是從 1 開始的,所以 `coins` 的索引是 `i-1` 時表示第 `i` 個硬幣的面值。 `dp[i][j-coins[i-1]]` 也不難理解,如果你決定使用這個面值的硬幣,那麼就應該關注如何湊出金額 `j - coins[i-1]`。 比如說,你想用面值為 2 的硬幣湊出金額 5,那麼如果你知道了湊出金額 3 的方法,再加上一枚面額為 2 的硬幣,不就可以湊出 5 了嘛。 **綜上就是兩種選擇,而我們想求的 `dp[i][j]` 是「共有多少種湊法」,所以 `dp[i][j]` 的值應該是以上兩種選擇的結果之和**: ```java for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) { if (j - coins[i-1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j-coins[i-1]]; return dp[N][W] ``` **最後一步,把偽碼翻譯成程式碼,處理一些邊界情況**。 我用 Java 寫的程式碼,把上面的思路完全翻譯了一遍,並且處理了一些邊界問題: ```java int change(int amount, int[] coins) { int n = coins.length; int[][] dp = amount int[n + 1][amount + 1]; // base case for (int i = 0; i <= n; i++) dp[i][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= amount; j++) if (j - coins[i-1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i-1]]; else dp[i][j] = dp[i - 1][j]; } return dp[n][amount]; } ``` 而且,我們通過觀察可以發現,`dp` 陣列的轉移只和 `dp[i][..]` 和 `dp[i-1][..]` 有關,所以可以壓縮狀態,進一步降低演算法的空間複雜度: ```java int change(int amount, int[] coins) { int n = coins.length; int[] dp = new int[amount + 1]; dp[0] = 1; // base case for (int i = 0; i < n; i++) for (int j = 1; j <= amount; j++) if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j-coins[i]]; return dp[amount]; } ``` 這個解法和之前的思路完全相同,將二維 `dp` 陣列壓縮為一維,時間複雜度 O(N\*amount),空間複雜度 O(amount)。 至此,這道零錢兌換問題也通過揹包問題的框架解決了。 **_____________** 我的 [線上電子書](https://labuladong.gitbook.io/algo) 有 100 篇原創文章,手把手帶刷 200 道力扣題目,建議收藏!對應的 GitHub [演算法倉庫](https://github.com/labuladong/fucking-algorithm) 已經獲得了 70k star,歡迎

版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
https://www.itread01.com/content/1604498954.html