完全背包理論

有N件物品和一個最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品都有無限個（也就是可以放入背包多次），求解將哪些物品裝入背包里物品價值總和最大。

示例：

背包最大重量為4。

物品為：

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

每件商品都有無限個！

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

完全背包和01背包問題唯一不同的地方就是，每種物品有無限件。

同樣leetcode上沒有純完全背包問題，都是需要完全背包的各種應(yīng)用，需要轉(zhuǎn)化成完全背包問題，所以這里還是以純完全背包問題進行講解理論和原理。

01背包和完全背包唯一不同就是體現(xiàn)在遍歷順序上，因此直接針對遍歷順序經(jīng)行分析！01背包內(nèi)嵌的循環(huán)是從大到小遍歷，為了保證每個物品僅被添加一次，而完全背包的物品是可以多次添加的，所以這里就要從小到達遍歷。

其次是先后問題，為什么遍歷物品在外層循環(huán)，遍歷背包容量在內(nèi)層循環(huán)？

在01背包中，如果是定義了二維數(shù)組，則先遍歷誰都可以，而定義一維數(shù)組后，兩個for循環(huán)先后循序一定是先遍歷物品，再遍歷背包容量。

在完全背包中，對于一維dp數(shù)組來說，其實兩個for循環(huán)嵌套順序是無所謂的！因為dp[j] 是根據(jù) 下標j之前所對應(yīng)的dp[j]計算出來的。 只要保證下標j之前的dp[j]都是經(jīng)過計算的就可以了。

遍歷物品在外層循環(huán)，遍歷背包容量在內(nèi)層循環(huán)，狀態(tài)如圖：

遍歷背包容量在外層循環(huán)，遍歷物品在內(nèi)層循環(huán)，狀態(tài)如圖：

因此，完全背包中，兩個for循環(huán)的先后循序，都不影響計算dp[j]所需要的值（這個值就是下標j之前所對應(yīng)的dp[j]）

518.零錢兌換II

給定不同面額的硬幣和一個總金額。寫出函數(shù)來計算可以湊成總金額的硬幣組合數(shù)。假設(shè)每一種面額的硬幣有無限個。

示例 1:

• 輸入: amount = 5, coins = [1, 2, 5]
• 輸出: 4

解釋: 有四種方式可以湊成總金額:

• 5=5
• 5=2+2+1
• 5=2+1+1+1
• 5=1+1+1+1+1

示例 2:

• 輸入: amount = 3, coins = [2]
• 輸出: 0
• 解釋: 只用面額2的硬幣不能湊成總金額3。

示例 3:

• 輸入: amount = 10, coins = [10]
• 輸出: 1

注意，你可以假設(shè)：

• 0 <= amount (總金額) <= 5000
• 1 <= coin (硬幣面額)?<= 5000
• 硬幣種類不超過 500 種
• 結(jié)果符合 32 位符號整數(shù)

本題可以重復(fù)放入金幣，也就是物品，因此屬于完全背包問題。轉(zhuǎn)換為背包問題就是：

1. 確定dp數(shù)組以及下標的含義：dp[j]為湊成總金額j的貨幣組合數(shù)
2. 確定遞推公式：dp[j] 就是所有的dp[j - coins[i]]想加的情況。dp[j]+=dp[j-coins[i]]
3. dp數(shù)組如何初始化：當金幣總額為0的時候，就只有一種情況，不放入金幣，所以dp[0]=1
4. 確定遍歷順序：在完全背包中，先遍歷背包或者物品都是可以的。因為純完全背包求得裝滿背包的最大價值是多少，和湊成總和的元素有沒有順序沒關(guān)系，所以純完全背包是能湊成總和就行，不用管怎么湊的。但本題要求湊成總和的組合數(shù)，元素之間明確要求沒有順序：那么如果外層for循環(huán)遍歷物品（錢幣），內(nèi)層for遍歷背包（金錢總額）的情況，假設(shè)：coins[0] = 1，coins[1] = 5。就是先把1加入計算，然后再把5加入計算，得到的方法數(shù)量只有{1, 5}這種情況。而不會出現(xiàn){5, 1}的情況。所以這種遍歷順序中dp[j]里計算的是組合數(shù)！如果把兩個for交換順序，那么背包容量的每一個值，都是經(jīng)過 1 和 5 的計算，包含了{1, 5} 和 {5, 1}兩種情況，此時計算的是排列數(shù)，本題要求不重復(fù)，只計算組合數(shù)即可，所以需要先遍歷物品，再遍歷背包。

class Solution {
    /**
    dp[j]為湊成總金額j的貨幣組合數(shù)
    dp[0]=1
    dp[j]+=dp[j-coins[i]]
     */
    public int change(int amount, int[] coins) {
        int[] dp= new int[amount+1];
        dp[0]=1;
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
}

377. 組合總和 Ⅳ

給定一個由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組，找出和為給定目標正整數(shù)的組合的個數(shù)。

示例:

• nums = [1, 2, 3]
• target = 4

所有可能的組合為： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

請注意，順序不同的序列被視作不同的組合。

因此輸出為 7

本題可以重復(fù)放物品，所以為完全背包問題，思考下面五部曲：

1. 確定dp數(shù)組以及下標的含義：dp[j]為湊成目標j的元素組合數(shù)
2. 確定遞推公式：dp[j]+=dp[j-nums[i]]
3. dp數(shù)組如何初始化：dp[0]=1
4. 確定遍歷順序：題里給的示例很明確的說民反，順序不同的序列視作不同的組合，也就是{1,2}和{2,1}算兩種組合，因此這里需要計算的是排列數(shù)，因此需要先遍歷背包，再遍歷物品。

本題再次強調(diào)的一點：文章來源地址http://www.zghlxwxcb.cn/news/detail-843252.html

• 如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層for遍歷背包。
• 如果求排列數(shù)就是外層for遍歷背包，內(nèi)層for循環(huán)遍歷物品。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0]=1;
        //求排列個數(shù)，需要先遍歷背包再遍歷物品
        for(int j=0;j<=target;j++){
            for(int i=0;i<nums.length;i++){
                if(j-nums[i]>=0 ) dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}

到了這里，關(guān)于Leetcoder Day39｜ 動態(tài)規(guī)劃part06 完全背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！