本周算法：背包问题-Java开发Java经验技巧

《本周算法：背包问题-Java开发Java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、木周算法：背包问题-编程开发技术本周算法：背包问题木文由ImportNew・hejiani翻译自javacodegeeks<>欢迎加入翻译小组。转载请见文末要求。背包问题很冇意思，同时也富冇挑战性。首先看一下这个问题的完整描述：问题假定背包的最大容量为w,N件物品，毎件物品都有自己的价值和重量，将物品放入背包屮使得背包内物品的总价值最大。背包问题wiki可以想彖这样一个场景一一小偷在屋子里偷东西，他带着一只背包。屋子里物品数量有限——每件物詁都具有一定的重量和价值——珠宝重量轻但价值高，桌子重但价值低。最重要的是小偷背包容

2、量有限。很明显，他不能把桌子分成两份或者带走珠宝的3/4o对于一件物甜他只能选择带走或者不带走。示例:KnapsackMaxweightTotalitemsValuesofitemsW二10(units)N=4v[]={10,40,30,50}从示例数据大致估算一下，最大重量为10时苗包能容纳的物品最大价值为50+40=90,重量为7。解决方法：最佳的解决方法是使用动态规划一一先得到该问题的局部解然后扩展到全局问题解。构建物品X在不同重量时的价值数组V（Value数组）:V[N][W]二4rows*10columns该矩阵

3、中的每个值的求解都代表一个更小的背包问题。初始情况一：对于第0列，它的含义是背包的容量为0。此时物品的价值呢？没有。因此，第一列都填入0。初始情况二：对于第0行，它的含义是屋内没有物站。那么没有任何物品的背包里的价值多少呢？还是没有！所有都是0。步骤：1、现在，开始填入数组每一行的值。第1行第1列代表什么含义呢？对于第一个物品，可以把重量为1的该物品放入背包吗？不行。第一个物品的重量是5。因此，填入0。实际上直到第5列（重量5）之前都应该填入0。2、对于第1行的第5列（重量5），意味着将物品1放入背包。填入10（注意,这是

4、Value数组）：3、继续，对于第6列，我们可以再放入重量为1（重量值-物品的重量）的物品吗。我们现在只考虑物品k由于我们加入物品1Z后就不能再加入额外的重量,可以很直观地看到其余的列都应该还是相同的值。4、接着，冇意思的事情就要出现了。在第3行第4列，此时重量为4。需要作以下判断：1.可以放入物品2吗——可以。物品2的重量为402.不加入物品2的话当前已有物品的重量的Value值是否更人——杏看相同重虽时的询-•行的值。不是。询一行的值为0,重量4时不能放入物品1。3.在这个重量时可以放入两件物品使得价值最大吗？——不能

5、。此时重量减去物品2的重最后为0o为什么是前一行?简单來说，重量为4的前一行的值木身就是个更小的背包问题解，它的含义是到该重量时背包内物品的最大价值（通过遍历物品得到）。举个例子：1.当前物品价值=402.当前物品重量二41.剩余重量=4-4二02.查看上而的行（物品1或者其余行的值）。剩余容量为0时，可以再容纳物品1吗?对于该给定的重量值上面的行还有任何值吗？计算过程如下：1）计算不放入该物品时该重量的最大价值:previousrow,sameweight二0=>V[item~l][weight]2）计算当前物品的价值+

6、可以容纳的剩余重量的价值Valueofcurrentitem+valueinpreviousrowwithweight4（totalweightunti1now（4）-weightofthecurrentitem（4））=>val[item-1]+V[item-1][weight-wt[item-1]]找到二者之中的最大值40（0和40）o3）下一次最重要的位置为第2行第9列。意味着此时重量为9,放入两件物品。根据示例数据现在可以放入两件物品。我们作了以下判断：1.Thevalueofthecurrentitem=402.

7、Theweightofthecurrentitem二43.Theweightthatisleftover二9-4二54.Checktherowabovc.Atthercmainingweight5,arcweabletoaccommodateItem1.计算如下：1.不加入该物晶时该重量的最大价值：previousrow,sameweight=101.计算当前物品的价值+可以容纳的剩余重量的价值Valueofcurrentitem(40)+valueinpreviousrowwithweight5(totalweightu

8、ntilnow(9)-weightofthecurrentitem(4))二1010vs50二50o解决了所有的子问题之后，返回V[N][W]的值一一4件物品重量为10时：复杂度解法的复朵度非常直观。在N次循环中有W次循环二〉0(NW)实现Java代码实现:classKnapsack{publicsta