devbox
盐析白兔
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

完全背包总结二

作者：盐析白兔 | 2024-02-15 13:46:07

赞

踩

完全背包总结二

1.完全背包和0/1背包的区别？

完全背包的物体有无限个，可以多次放入

0/1背包的物体只有一个，只能放入一次

2.关于物品遍历顺序

在0/1背包中为了防止物品被重复放入，所以选择倒序遍历背包

而完全背包中，可以重复放入，所以选择正序遍历背包

具体来说，如题目

重量价值
物品1115
物品2320
物品3535

求大小为4的背包可获得的最大价值。

（1）对于0/1背包来说：各个物品只能放入一次

  1. package other;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Objects;
  5.  
  6. public class Bag {
  7.     public static void main(String[] args) {
  8.         int[] weight=new int[]{1,3,4};
  9.         int[] values=new int[]{15,20,30};
  10.         Bag obj=new Bag();
  11.         System.out.println("result: "+ obj.simpleBag2(weight,values,4));
  12.     }
  13.  
  14.     public int simpleBag2(int[] weight,int[] values,int bag){
  15.         int dp[]=new int[bag+1];
  16.         //初始化
  17.         Arrays.fill(dp,0);
  18.         //双层for循环
  19.         for(int i=0;i<weight.length;i++){//遍历物品
  20.             for(int j=bag;j>=0;j--){//遍历背包
  21.                 System.out.println("拿起物品i="+i+"  ,\t重量:"+weight[i]+"\t背包容量:"+j);
  22.                 if(weight[i]<=j){
  23.                     dp[j]=Math.max(dp[j],dp[j-weight[i]]+values[i]);
  24.                     System.out.println("放入物品i="+i+"  ,\t价值:"+values[i]);
  25.                 } else {
  26.                     dp[j]=dp[j];
  27.                     System.out.println("不放入物品i="+i);
  28.                 }
  29.                 printArr(j,dp);
  30.             }
  31.         }
  32.         printArr(null,dp);
  33.         return dp[dp.length-1];
  34.     }
  35.  
  36.    
  37.     public void printArr(Integer j,int []arr){
  38.         if(!Objects.isNull(j)){
  39.             System.out.print("j = "+j+"  :\t\t");
  40.         }
  41.         for(int i=0;i<arr.length;i++){
  42.             System.out.print(arr[i]+"\t");
  43.         }
  44.         System.out.println();
  45.     }
  46. }

拿起物品i=0  ,    重量:1    背包容量:4
放入物品i=0  ,    价值:15
j = 4  :        0    0    0    0    15    
拿起物品i=0  ,    重量:1    背包容量:3
放入物品i=0  ,    价值:15
j = 3  :        0    0    0    15    15    
拿起物品i=0  ,    重量:1    背包容量:2
放入物品i=0  ,    价值:15
j = 2  :        0    0    15    15    15    
拿起物品i=0  ,    重量:1    背包容量:1
放入物品i=0  ,    价值:15
j = 1  :        0    15    15    15    15    
拿起物品i=0  ,    重量:1    背包容量:0
不放入物品i=0
j = 0  :        0    15    15    15    15    
拿起物品i=1  ,    重量:3    背包容量:4
放入物品i=1  ,    价值:20
j = 4  :        0    15    15    15    35    
拿起物品i=1  ,    重量:3    背包容量:3
放入物品i=1  ,    价值:20
j = 3  :        0    15    15    20    35    
拿起物品i=1  ,    重量:3    背包容量:2
不放入物品i=1
j = 2  :        0    15    15    20    35    
拿起物品i=1  ,    重量:3    背包容量:1
不放入物品i=1
j = 1  :        0    15    15    20    35    
拿起物品i=1  ,    重量:3    背包容量:0
不放入物品i=1
j = 0  :        0    15    15    20    35    
拿起物品i=2  ,    重量:4    背包容量:4
放入物品i=2  ,    价值:30
j = 4  :        0    15    15    20    35    
拿起物品i=2  ,    重量:4    背包容量:3
不放入物品i=2
j = 3  :        0    15    15    20    35    
拿起物品i=2  ,    重量:4    背包容量:2
不放入物品i=2
j = 2  :        0    15    15    20    35    
拿起物品i=2  ,    重量:4    背包容量:1
不放入物品i=2
j = 1  :        0    15    15    20    35    
拿起物品i=2  ,    重量:4    背包容量:0
不放入物品i=2
j = 0  :        0    15    15    20    35    
0    15    15    20    35    
result: 35

可以观察到，由于dp[i]总是由前面的dp[i-1]推导来的，但是每次更新时，dp[i-1]没有物品的累积。

（2）对于完全背包来说：物品可以重复放入

  1. package other;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Objects;
  5.  
  6. public class Bag {
  7.     public static void main(String[] args) {
  8.         int[] weight=new int[]{1,3,4};
  9.         int[] values=new int[]{15,20,30};
  10.         Bag obj=new Bag();
  11.         System.out.println("result: "+ obj.simpleBag(weight,values,4));
  12.     }
  13.  
  14.  
  15.     public int simpleBag(int[] weight,int[] values,int bag){
  16.         int dp[]=new int[bag+1];
  17.         //初始化
  18.         Arrays.fill(dp,0);
  19.         //双层for循环
  20.         for(int i=0;i<weight.length;i++){//遍历物品
  21.             for(int j=1;j<=bag;j++){//遍历背包
  22.                 System.out.println("拿起物品i="+i+"  ,\t重量:"+weight[i]+"\t背包容量:"+j);
  23.                 if(weight[i]<=j){
  24.                     dp[j]=Math.max(dp[j],dp[j-weight[i]]+values[i]);
  25.                     System.out.println("放入物品i="+i+"  ,\t价值:"+values[i]);
  26.                 } else {
  27.                     dp[j]=dp[j];
  28.                     System.out.println("不放入物品i="+i);
  29.                 }
  30.                 printArr(j,dp);
  31.             }
  32.         }
  33.         printArr(null,dp);
  34.         return dp[dp.length-1];
  35.     }
  36.  
  37.     public void printArr(Integer j,int []arr){
  38.         if(!Objects.isNull(j)){
  39.             System.out.print("j = "+j+"  :\t\t");
  40.         }
  41.         for(int i=0;i<arr.length;i++){
  42.             System.out.print(arr[i]+"\t");
  43.         }
  44.         System.out.println();
  45.     }
  46. }

拿起物品i=0  ,    重量:1    背包容量:1
放入物品i=0  ,    价值:15
j = 1  :        0    15    0    0    0    
拿起物品i=0  ,    重量:1    背包容量:2
放入物品i=0  ,    价值:15
j = 2  :        0    15    30    0    0    
拿起物品i=0  ,    重量:1    背包容量:3
放入物品i=0  ,    价值:15
j = 3  :        0    15    30    45    0    
拿起物品i=0  ,    重量:1    背包容量:4
放入物品i=0  ,    价值:15
j = 4  :        0    15    30    45    60    
拿起物品i=1  ,    重量:3    背包容量:1
不放入物品i=1
j = 1  :        0    15    30    45    60    
拿起物品i=1  ,    重量:3    背包容量:2
不放入物品i=1
j = 2  :        0    15    30    45    60    
拿起物品i=1  ,    重量:3    背包容量:3
放入物品i=1  ,    价值:20
j = 3  :        0    15    30    45    60    
拿起物品i=1  ,    重量:3    背包容量:4
放入物品i=1  ,    价值:20
j = 4  :        0    15    30    45    60    
拿起物品i=2  ,    重量:4    背包容量:1
不放入物品i=2
j = 1  :        0    15    30    45    60    
拿起物品i=2  ,    重量:4    背包容量:2
不放入物品i=2
j = 2  :        0    15    30    45    60    
拿起物品i=2  ,    重量:4    背包容量:3
不放入物品i=2
j = 3  :        0    15    30    45    60    
拿起物品i=2  ,    重量:4    背包容量:4
放入物品i=2  ,    价值:30
j = 4  :        0    15    30    45    60    
0    15    30    45    60    
result: 60

可以观察到物品被重复放入

（3）对于0/1背包问题，双for循环顺序能否颠倒

尝试先背包后物品，是否会对结果有影响

  1. public int simpleBag3(int[] weight,int[] values,int bag){
  2.         int dp[]=new int[bag+1];
  3.         //初始化
  4.         Arrays.fill(dp,0);
  5.         //双层for循环
  6.  
  7.         for(int j=bag;j>=0;j--){//遍历背包
  8.             for(int i=0;i<weight.length;i++){//遍历物品
  9.                 System.out.println("拿起物品i="+i+"  ,\t重量:"+weight[i]+"\t背包容量:"+j);
  10.                 if(weight[i]<=j){
  11.                     dp[j]=Math.max(dp[j],dp[j-weight[i]]+values[i]);
  12.                     System.out.println("放入物品i="+i+"  ,\t价值:"+values[i]);
  13.                 } else {
  14.                     dp[j]=dp[j];
  15.                     System.out.println("不放入物品i="+i);
  16.                 }
  17.                 printArr(j,dp);
  18.             }
  19.         }
  20.         printArr(null,dp);
  21.         return dp[dp.length-1];
  22.     }


拿起物品i=0  ,    重量:1    背包容量:4
放入物品i=0  ,    价值:15
j = 4  :        0    0    0    0    15    
拿起物品i=1  ,    重量:3    背包容量:4
放入物品i=1  ,    价值:20
j = 4  :        0    0    0    0    20    
拿起物品i=2  ,    重量:4    背包容量:4
放入物品i=2  ,    价值:30
j = 4  :        0    0    0    0    30    
拿起物品i=0  ,    重量:1    背包容量:3
放入物品i=0  ,    价值:15
j = 3  :        0    0    0    15    30    
拿起物品i=1  ,    重量:3    背包容量:3
放入物品i=1  ,    价值:20
j = 3  :        0    0    0    20    30    
拿起物品i=2  ,    重量:4    背包容量:3
不放入物品i=2
j = 3  :        0    0    0    20    30    
拿起物品i=0  ,    重量:1    背包容量:2
放入物品i=0  ,    价值:15
j = 2  :        0    0    15    20    30    
拿起物品i=1  ,    重量:3    背包容量:2
不放入物品i=1
j = 2  :        0    0    15    20    30    
拿起物品i=2  ,    重量:4    背包容量:2
不放入物品i=2
j = 2  :        0    0    15    20    30    
拿起物品i=0  ,    重量:1    背包容量:1
放入物品i=0  ,    价值:15
j = 1  :        0    15    15    20    30    
拿起物品i=1  ,    重量:3    背包容量:1
不放入物品i=1
j = 1  :        0    15    15    20    30    
拿起物品i=2  ,    重量:4    背包容量:1
不放入物品i=2
j = 1  :        0    15    15    20    30    
拿起物品i=0  ,    重量:1    背包容量:0
不放入物品i=0
j = 0  :        0    15    15    20    30    
拿起物品i=1  ,    重量:3    背包容量:0
不放入物品i=1
j = 0  :        0    15    15    20    30    
拿起物品i=2  ,    重量:4    背包容量:0
不放入物品i=2
j = 0  :        0    15    15    20    30    
0    15    15    20    30    
result: 30

为了保证物品只用一次，所以背包的遍历一定是倒序遍历，颠倒双for的遍历顺序是先背包后物品

保证了防止最合适的一个物品，由于左边的背包没有计算，所以无法累计物品的重量

最后只是选择了能放入了一个最合适的物品

所以这种方式是不可以的。

（4）对于完全背包问题，双for循环顺序能否颠倒

尝试先背包后物品，是否会对结果有影响

  1. public int simpleBag4(int[] weight,int[] values,int bag){
  2.         int dp[]=new int[bag+1];
  3.         //初始化
  4.         Arrays.fill(dp,0);
  5.         //双层for循环
  6.  
  7.         for(int j=1;j<=bag;j++){//遍历背包
  8.             for(int i=0;i<weight.length;i++){//遍历物品
  9.                 System.out.println("拿起物品i="+i+"  ,\t重量:"+weight[i]+"\t背包容量:"+j);
  10.                 if(weight[i]<=j){
  11.                     dp[j]=Math.max(dp[j],dp[j-weight[i]]+values[i]);
  12.                     System.out.println("放入物品i="+i+"  ,\t价值:"+values[i]);
  13.                 } else {
  14.                     dp[j]=dp[j];
  15.                     System.out.println("不放入物品i="+i);
  16.                 }
  17.                 printArr(j,dp);
  18.             }
  19.         }
  20.         printArr(null,dp);
  21.         return dp[dp.length-1];
  22.     }
  1. 拿起物品i=0  ,	重量:1	背包容量:1
  2. 放入物品i=0  ,	价值:15
  3. j = 1  :		0	15	0	0	0	
  4. 拿起物品i=1  ,	重量:3	背包容量:1
  5. 不放入物品i=1
  6. j = 1  :		0	15	0	0	0	
  7. 拿起物品i=2  ,	重量:4	背包容量:1
  8. 不放入物品i=2
  9. j = 1  :		0	15	0	0	0	
  10. 拿起物品i=0  ,	重量:1	背包容量:2
  11. 放入物品i=0  ,	价值:15
  12. j = 2  :		0	15	30	0	0	
  13. 拿起物品i=1  ,	重量:3	背包容量:2
  14. 不放入物品i=1
  15. j = 2  :		0	15	30	0	0	
  16. 拿起物品i=2  ,	重量:4	背包容量:2
  17. 不放入物品i=2
  18. j = 2  :		0	15	30	0	0	
  19. 拿起物品i=0  ,	重量:1	背包容量:3
  20. 放入物品i=0  ,	价值:15
  21. j = 3  :		0	15	30	45	0	
  22. 拿起物品i=1  ,	重量:3	背包容量:3
  23. 放入物品i=1  ,	价值:20
  24. j = 3  :		0	15	30	45	0	
  25. 拿起物品i=2  ,	重量:4	背包容量:3
  26. 不放入物品i=2
  27. j = 3  :		0	15	30	45	0	
  28. 拿起物品i=0  ,	重量:1	背包容量:4
  29. 放入物品i=0  ,	价值:15
  30. j = 4  :		0	15	30	45	60	
  31. 拿起物品i=1  ,	重量:3	背包容量:4
  32. 放入物品i=1  ,	价值:20
  33. j = 4  :		0	15	30	45	60	
  34. 拿起物品i=2  ,	重量:4	背包容量:4
  35. 放入物品i=2  ,	价值:30
  36. j = 4  :		0	15	30	45	60	
  37. 0	15	30	45	60	
  38. result: 60
  39.  
  40. Process finished with exit code 0

所以，对于完全背包来说，只是更新的方式不一样，结果是一样的。

先物品后背包<=>行更新

先背包后物品<=>列更新

3.总结

0/1背包问题：

        双for循环的的顺序不可以颠倒

        背包倒序遍历才能保证物品取用一次

完全背包问题：

        双for循环顺序可以颠倒，只是更新是行更新还是列更新的问题

        背包正序，每个物品都可以取用无限次。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号