背包问题很有意思,同时也富有挑战性。首先看一下这个问题的完整描述: 问题假定背包的最大容量为W,N件物品,每件物品都有自己的价值和重量,将物品放入背包中使得背包内物品的总价值最大。 可以想象这样一个场景——小偷在屋子里偷东西,他带着一只背包。屋子里物品数量有限——每件物品都具有一定的重量和价值——珠宝重量轻但价值高,桌子重但价值低。最重要的是小偷背包容量有限。很明显,他不能把桌子分成两份或者带走珠宝的3/4。对于一件物品他只能选择带走或者不带走。 示例:
从示例数据大致估算一下,最大重量为10时背包能容纳的物品最大价值为50+40=90,重量为7。 解决方法:最佳的解决方法是使用动态规划——先得到该问题的局部解然后扩展到全局问题解。 构建物品X在不同重量时的价值数组V(Value数组):
该矩阵中的每个值的求解都代表一个更小的背包问题。 初始情况一:对于第0列,它的含义是背包的容量为0。此时物品的价值呢?没有。因此,第一列都填入0。 初始情况二:对于第0行,它的含义是屋内没有物品。那么没有任何物品的背包里的价值多少呢?还是没有!所有都是0。 步骤: 1、现在,开始填入数组每一行的值。第1行第1列代表什么含义呢?对于第一个物品,可以把重量为1的该物品放入背包吗?不行。第一个物品的重量是5。因此,填入0。实际上直到第5列(重量5)之前都应该填入0。 3、继续,对于第6列,我们可以再放入重量为1(重量值-物品的重量)的物品吗。我们现在只考虑物品1。由于我们加入物品1之后就不能再加入额外的重量,可以很直观地看到其余的列都应该还是相同的值。 4、接着,有意思的事情就要出现了。在第3行第4列,此时重量为4。 需要作以下判断:
为什么是前一行?简单来说,重量为4的前一行的值本身就是个更小的背包问题解,它的含义是到该重量时背包内物品的最大价值(通过遍历物品得到)。 举个例子:
计算过程如下: 1) 计算不放入该物品时该重量的最大价值:
2) 计算当前物品的价值 + 可以容纳的剩余重量的价值
找到二者之中的最大值40(0和40)。 3) 下一次最重要的位置为第2行第9列。意味着此时重量为9,放入两件物品。根据示例数据现在可以放入两件物品。我们作了以下判断:
计算如下:
10vs50 = 50。 解决了所有的子问题之后,返回V[N][W]的值——4件物品重量为10时: 复杂度解法的复杂度非常直观。在N次循环中有W次循环 => O(NW) 实现Java代码实现:
译文链接: http://www./13072.html [ 转载请保留原文出处、译者和译文链接。] |
|