完全背包理论

阳光穿透心脏的1/2处 2024-03-25 14:03 41阅读 0赞

### 完全背包 ###

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。  
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。  
同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。  
在下面的讲解中，我依然举这个例子：  
背包最大重量为4。  
物品为：  
![在这里插入图片描述][b7d3d90faffe4a8fad47a69a2fd407b3.png]  
每件商品都有无限个！  
问背包能背的物品最大价值是多少？  
01背包和完全背包唯一不同就是体现在遍历顺序上

[https://donglin.blog.csdn.net/article/details/129412502][https_donglin.blog.csdn.net_article_details_129412502]  
[https://donglin.blog.csdn.net/article/details/129437136][https_donglin.blog.csdn.net_article_details_129437136]  
首先在回顾一下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] = Mathmax(dp[j], dp[j - weight[i]] + value[i]);
    
        }
    }

dp状态图如下：  
![在这里插入图片描述][a4f2f922f5ef49728080b247d51cb355.png]  
代码测试

//先遍历物品，再遍历背包
        private static void testCompletePack(){
        
            int[] weight = {
        1, 3, 4};
            int[] value = {
        15, 20, 30};
            int bagWeight = 4;
            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]);
                }
            }
            for (int maxValue : dp){
        
                System.out.println(maxValue + "   ");
            }
        }
    
        //先遍历背包，再遍历物品
        private static void testCompletePackAnotherWay(){
        
            int[] weight = {
        1, 3, 4};
            int[] value = {
        15, 20, 30};
            int bagWeight = 4;
            int[] dp = new int[bagWeight + 1];
            for (int i = 1; i <= bagWeight; i++){
         // 遍历背包容量
                for (int j = 0; j < weight.length; j++){
         // 遍历物品
                    if (i - weight[j] >= 0){
        
                        dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
                    }
                }
            }
            for (int maxValue : dp){
        
                System.out.println(maxValue + "   ");
            }
        }
    
        public static void main(String[] args) {
        
            testCompletePack();
            testCompletePackAnotherWay();
        }

[b7d3d90faffe4a8fad47a69a2fd407b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3994333d10914032837e4d4d591b9508.png
[https_donglin.blog.csdn.net_article_details_129412502]: https://donglin.blog.csdn.net/article/details/129412502
[https_donglin.blog.csdn.net_article_details_129437136]: https://donglin.blog.csdn.net/article/details/129437136
[a4f2f922f5ef49728080b247d51cb355.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/24aa87ccbd694f50bba7ae3aeb72b20f.png