動态規劃完全背包

完全背包

和01背包一樣力扣上沒有沒有純完全背包問題，都是需要完全背包的各種應⽤，需要轉化成完全背包問題，是以我們這⾥還是以純完全背包問題來讨論其理論和原理。

有N件物品和⼀個最多能背重量為W的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品都有⽆限個（也就是可以放⼊背包多次），求解将哪些物品裝⼊背包⾥物品價值總和最⼤。 完全背包和01背包問題唯⼀不同的地⽅就是，每種物品有⽆限件。

題：背包最⼤重量為4。

物品為：

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

因為01背包和完全背包唯⼀不同就是展現在周遊順序上，是以本⽂就不去做動規五部曲了，我們直接針對周遊順序經⾏分析！

⾸先在回顧⼀下01背包周遊順序的核⼼代碼：

for (int i = 0; i < weight.length; i++) {//周遊物品
            for (int j = bagWeight; j >= weight[i]; j--) {背包容量
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }      

我們知道01背包内嵌的循環是從⼤到⼩周遊，為了保證每個物品僅被添加⼀次。

⽽完全背包的物品是可以添加多次的，是以可以而且需要從⼩到⼤去周遊，即：

for (int i = 0; i < weight.length; i++) {//周遊物品
            for (int j = weight[i]; j < bagWeight; j++) {背包容量
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }      

dp狀态圖如下：

到這裡就可以進行解題了，其實還有⼀個很重要的問題，為什麼周遊物品在外層循環，周遊背包容量在内層循環？

這個問題很多地方關于這⾥都是輕描淡寫就略過了，⼤家都預設 周遊物品在外層，周遊背包容量在内層，好像本應該如此⼀樣，那麼為什麼呢？難道就不能周遊背包容量在外層，周遊物品在内層？

在之前01背包問題的文章中我們就提到過很多次。01背包中⼆維dp數組的兩個for周遊的先後循序是可以颠倒了，一維dp數組的兩個for循環先後循序⼀定是先周遊物品，再周遊背包容量。就是為了防止重複放入物品，而在完全背包中應為物品可以是無限次使用，是以對于⼀維dp數組來說，其實兩個for循環嵌套順序同樣⽆所謂！而且在完全背包中dp[j] 是根據 下标j之前所對應的dp[j]計算出來的。 隻要保證下标j之前的dp[j]都是經過計算的就可以了。周遊物品在外層循環，周遊背包容量在内層循環，狀态如圖：

周遊背包容量在外層循環，周遊物品在内層循環，狀态如圖：

for (int i = 0; i <= bagWeight; i++)
    for (int j = 0; j < weight.length; j++)
        if (i >= weight[j])
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);      

public int dp(int[] weight, int[] value, int bagWeight){
        int[] dp = new int[bagWeight + 1];
        for (int i = 0; i < weight.length; i++)
            for (int j = weight[i]; j <= bagWeight; j++)
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        return  dp[bagWeight];
}      

public int dp(int[] weight, int[] value, int bagWeight){
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i <= bagWeight; i++)
        for (int j = 0; j < weight.length; j++)
            if (i >= weight[j])
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    return  dp[bagWeight];
}