动态规划完全背包

客官°小女子只卖身不卖艺 2023-09-27 12:32 112阅读 0赞

## 完全背包 ##

和01背包一样力扣上没有没有纯完全背包问题，都是需要完全背包的各种应⽤，需要转化成完全背包问题，所以我们这⾥还是以纯完全背包问题来讨论其理论和原理。  
有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品都有⽆限个（也就是可以放⼊背包多次），求解将哪些物品装⼊背包⾥物品价值总和最⼤。 完全背包和01背包问题唯⼀不同的地⽅就是，每种物品有⽆限件。  
题：背包最⼤重量为4。  
物品为：

![b60a3b3c4de2544f0b290a050fa300a9.png][]

问背包能背的物品最⼤价值是多少？

因为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状态图如下：

![69c0ced1929db37adf529a5dcffdaecb.png][]

到这里就可以进行解题了，其实还有⼀个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？  
这个问题很多地方关于这⾥都是轻描淡写就略过了，⼤家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此⼀样，那么为什么呢？难道就不能遍历背包容量在外层，遍历物品在内层？  
在之前01背包问题的文章中我们就提到过很多次。01背包中⼆维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序⼀定是先遍历物品，再遍历背包容量。就是为了防止重复放入物品，而在完全背包中应为物品可以是无限次使用，所以对于⼀维dp数组来说，其实两个for循环嵌套顺序同样⽆所谓！而且在完全背包中dp\[j\] 是根据 下标j之前所对应的dp\[j\]计算出来的。 只要保证下标j之前的dp\[j\]都是经过计算的就可以了。遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

![baea7cb3eb848fb7c51f82bc400c21f9.png][]

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

![916a6d36559d9fde94f46d18a896a882.png][]

看了这两个图，⼤家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp\[j\]所需要的值（这个值就是下标j之前所对应的dp\[j\]）。  
先遍历被背包在遍历物品，Java代码如下：

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]);

完整先遍历物品再遍历背包，Java代码如下：

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];
    }

完整先遍历背包再遍历物品，Java代码如下：

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];
    }

[b60a3b3c4de2544f0b290a050fa300a9.png]: https://img-blog.csdnimg.cn/img_convert/b60a3b3c4de2544f0b290a050fa300a9.png
[69c0ced1929db37adf529a5dcffdaecb.png]: https://img-blog.csdnimg.cn/img_convert/69c0ced1929db37adf529a5dcffdaecb.png
[baea7cb3eb848fb7c51f82bc400c21f9.png]: https://img-blog.csdnimg.cn/img_convert/baea7cb3eb848fb7c51f82bc400c21f9.png
[916a6d36559d9fde94f46d18a896a882.png]: https://img-blog.csdnimg.cn/img_convert/916a6d36559d9fde94f46d18a896a882.png