背包问题解法（背包问题）

大家好，小信来为大家解答以上问题。背包问题解法，背包问题很多人还不知道，现在让我们一起来看看吧！

1、 假设背包的最大容量是W，N件物品，每件物品都有自己的价值和重量，把物品放在背包里会使背包里物品的总价值最大化。

2、 背包问题维基

3、 想象这样一个场景：3354。一个小偷在房子里偷东西。他背着一个背包。房间里的物品数量是有限的。——每件物品都有一定的重量和价值。——珠宝重量轻但价值高。桌子

4、 重但价值低。最重要的是小偷的背包容量有限。很明显，他不能把桌子一分为二或者拿走3/4的珠宝。对于一件物品，他只能选择拿还是不拿。

5、 示例：

6、 背包最大重量：W=10(单位)

7、 项目总数：N=4

8、 项目的值：v[]={10，40，30，50}

9、 物品重量：w[]={5，4，6，3}

10、 从实例数据粗略估算，最大重量为10时，背包能装的物品最大值为50 40=90，重量为7。

11、 最好的解决方法是用动态规划——得到问题的局部解，然后扩展到全局解。

12、 以不同的权重构造项目X的值数组V(值数组):

13、 V[N][W]=4行* 10列

14、 这个矩阵中每个值的解代表一个更小的背包问题。

15、 初始情况1:对于0列，表示背包的容量为0。此时该物品的价值是多少？没有。因此，第一列用零填充。

16、 初始情况2:对于0线，表示家里没有物品。那么一个没有任何物品的背包有什么价值呢？还是不行！都是零。

17、 1.现在，开始填充数组中每行的值。第一行第一列是什么意思？第一件物品，可以把重量为1的物品放进背包吗？不会吧。第一件物品的重量是5。因此，填写0。其实0要一直填到第五列(权重5)。2.对于第1行第5列(重量5)，表示将物品1放入背包。填入10(注意这是一个值数组):

18、 3.继续。对于第6列，我们是否可以放入另一个权重为1的项目(权重值-项目的权重)？现在我们只考虑第一项。由于我们在添加第1项后不能添加额外的权重，因此可以直观地看到，其余的列应该仍然具有相同的值。

19、 4.然后，有趣的事情就会发生。在第3行第4列，权重是4。

20、 做出如下判断：

21、 1.你能加入第二项吗？——是的。2的重量是4。

22、 2.如果不添加项目2，当前已有项目的权重值是否更大？——找到相同重量时，检查前一行的值。不可以，上一行的值是0，权重为4时不能放置物品1。

23、 3.能不能在这个重量里放两个物品，让价值最大化？3354不行。此时重量减去物品2的重量为0。

24、 简单来说，前面那条本身重量为4的线的值更小背包问题解，表示背包中物品最多到这个重量的最大值(通过遍历物品得到)。

25、 例如：

26、 当前项目值=40

27、 当前项目权重=4

28、 剩余重量=4-4=0

29、 查看顶行(项目1或其余行的值)。剩余容量为0时，是否可以再次持有项目1？对于给定的重量值，上述行中有值吗？

30、 计算过程如下：

31、 1)计算物品未放入时的最大重量值：

32、 前一行，相同权重=0

33、 =V[项目-1][重量]

34、 2)计算当前项目的值可以容纳的剩余重量的值

35、 当前项目的值

36、 前一行中权重为4的值(到目前为止的总权重(4) -当前项目的权重(4))

37、 =val[项目-1]V[项目-1][weight-wt[项目-1]]

38、 求其中最大值40(0和40)。

39、 3)下次最重要的位置是第2行第9列。这意味着权重是9。放入两件物品。根据示例数据，现在可以放入两个项目。我们做出如下判断：

40、 1.当前项目的值=40

41、 2.当前项目的权重=4

42、 3.剩下的重量=9 - 4=5

43、 4.检查上面一行。在剩余重量为5的情况下，我们能够

44、 未添加物品时，该重量的最大值：

45、 前一行，相同重量=10

46、 计算当前项目的值和可容纳的剩余重量的值。

47、 当前项目的值(40)

48、 前一行中权重为5的值（到目前为止的总权重(9) -当前项目的权重(4))

49、 =10

50、 10vs50=50。

51、 解决了所有的子问题之后，返回V[N][W]的值——4件物品重量为10时：

52、 解法的复杂度非常直观。在普通次循环中有W次循环=O(西北)

53、 背包类{

54、 公共静态void main(String[] args)引发异常{

55、 int val[]={10，40，30，50 }；

56、 int wt[]={5，4，6，3 }；

57、 int W=10

58、 系统。出去。println(backpackage(val，wt，W))；

59、 }

60、 public static int backpack(int val[]，int wt[]，int W) {

61、 //获取项目总数。

62、 //可能是重量长度或阀门长度.这无关紧要

63、 int N=重量长度；

64、 //创建一个矩阵。

65、 //项目按行排列，每侧第一列的权重为

66、 int[][]V=new int[N 1][W 1]；

67、 //如果背包的容量是0集呢

68、 //第0行的所有列都为0

69、 for(int col=0；col=W；col ) {

70、 v[0]div class=' column col-1-2 ' p/p/div=0；

71、 }

72、 //家里没有物品怎么办。

73、 //用0填充第一行

74、 for(int row=0；row=N；row ) {

75、 v[row][0]=0；

76、 }

77、 for(int item=1；item=N；项目){

78、 //让我们逐行填充这些值

79、 for(int weight=1；重量=W；重量){

80、 //当前项目的重量减少了吗

81、 //大于或等于运行重量

82、 if(wt[item-1]=重量){

83、 //给定一个权重，检查当前

84、 //我们能负担得起的项目的项目值

85、 //剩余重量大于该值

86、 //没有当前项本身

87、 v[项目][重量]=数学。max(val[item-1]V[item-1][weight-wt[item-1]]，V[item-1][weight])；

88、 }

89、 否则{

90、 //如果当前项的权重大于

91、 //运行重量，只是结转数值

92、 //没有当前项目

93、 五[项目][重量]=V[项目-1][重量];

94、 }

95、 }

96、 }

97、 //打印矩阵

98、 for (int[] rows : V) {

99、 for (int col : rows) {

100、 System.out.format(']'，col)；

101、 }

102、 系统。出去。println()；

103、 }

104、 return V[N][W]；

105、 }

106、 }

本文到此结束，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！