在 / 背包问题中需对容量为c 的背包进行装载从n 个物品中选取装入背包的物品每件物品i 的重量为wi 价值为pi 对于可行的背包装载背包中物品的总重量不能超过背包的容量最佳装载是指所装入的物品价值最高即n ?i=pi xi 取得最大值约束条件为n ?i =wi xi≤c 和xi?[ ] ( ≤i≤n)
在这个表达式中需求出xt 的值xi = 表示物品i 装入背包中xi = 表示物品i 不装入背包 / 背包问题是一个一般化的货箱装载问题即每个货箱所获得的价值不同货箱装载问题转化为背包问题的形式为船作为背包货箱作为可装入背包的物品 例 在杂货店比赛中你获得了第一名奖品是一车免费杂货店中有n 种不同的货物规则规定从每种货物中最多只能拿一件车子的容量为c物品i 需占用wi 的空间价值为pi 你的目标是使车中装载的物品价值最大当然所装货物不能超过车的容量且同一种物品不得拿走多件这个问题可仿照 / 背包问题进行建模其中车对应于背包货物对应于物品
/ 背包问题有好几种贪婪策略每个贪婪策略都采用多步过程来完成背包的装入在每一步过程中利用贪婪准则选择一个物品装入背包一种贪婪准则为从剩余的物品中选出可以装入背包的价值最大的物品利用这种规则价值最大的物品首先被装入(假设有足够容量)然后是下一个价值最大的物品如此继续下去这种策略不能保证得到最优解例如考虑n= w=[] p =[] c = 当利用价值贪婪准则时获得的解为x= [ ]这种方案的总价值为 而最优解为[ ]其总价值为
另一种方案是重量贪婪准则是从剩下的物品中选择可装入背包的重量最小的物品虽然这种规则对于前面的例子能产生最优解但在一般情况下则不一定能得到最优解考虑n= w=[] p=[] c= 当利用重量贪婪策略时获得的解为x =[] 比最优解[ ]要差
还可以利用另一方案价值密度pi /wi 贪婪算法这种选择准则为从剩余物品中选择可装入包的pi /wi 值最大的物品这种策略也不能保证得到最优解利用此策略试解n= w=[] p=[] c= 时的最优解
我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧 / 背包问题是一个N P复杂问题对于这类问题也许根本就不可能找到具有多项式时间的算法虽然按pi /wi 非递(增)减的次序装入物品不能保证得到最优解但它是一个直觉上近似的解我们希望它是一个好的启发式算法且大多数时候能很好地接近最后算法在 个随机产生的背包问题中用这种启发式贪婪算法来解有 题为最优解有 个例子与最优解相差 %所有 个答案与最优解之差全在 %以内该算法能在O (nl o gn)时间内获得如此好的性能我们也许会问是否存在一个x (x< )使得贪婪启发法的结果与最优值相差在x%以内答案是否定的为说明这一点考虑例子n = w = [ y] p= [ y] 和c= y贪婪算法结果为x=[] 这种方案的值为 对于y≥ / 最优解的值为 y因此贪婪算法的值与最优解的差对最优解的比例为( ( y )/y* ) %对于大的y这个值趋近于 %但是可以建立贪婪启发式方法来提供解使解的结果与最优解的值之差在最优值的x% (x<) 之内首先将最多k 件物品放入背包如果这k 件物品重量大于c则放弃它否则剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解
例 考虑n = w=[] p=[] c = 当k= 时背包按物品价值密度非递减顺序装入首先将物品放入背包然后是物品背包剩下的容量为个单元剩下的物品没有一个合适的因此解为x = [ ]此解获得的价值为
现在考虑k = 时的贪婪启发法最初的子集为{ } { } { } { }子集{ } { }产生与k= 时相同的结果考虑子集{ }置x 为此时还剩个单位的容量按价值密度非递增顺序来考虑如何利用这个单位的容量首先考虑物品它适合因此取x 为这时仅剩下个单位容量了且剩余物品没有能够加入背包中的物品通过子集{ }开始求解得结果为x = [ ]获得的价值为 若从子集{ }开始产生的解为x = [ ]获得的价值为 考虑子集大小为和时获得的最优解为[ ]这个解是通过k= 的贪婪启发式算法得到的
若k= 除了考虑k< 的子集还必需考虑子集{ } { } { } { } { }和{ }首先从最后一个子集开始它是不可行的故将其抛弃剩下的子集经求解分别得到如下结果[ ] [ ] [ ] [ ]和[ ]这些结果中最后一个价值为 它的值比k= 和k= 时获得的解要高这个答案即为启发式方法产生的结果 这种修改后的贪婪启发方法称为k阶优化方法(k o p t i m a l)也就是若从答案中取出k 件物品并放入另外k 件获得的结果不会比原来的好而且用这种方式获得的值在最优值的( / (k + ) ) %以内当k= 时保证最终结果在最佳值的 %以内;当k= 时则在 %以内等等这种启发式方法的执行时间随k 的增大而增加需要测试的子集数目为O (nk )每一个子集所需时间为O (n)因此当k >时总的时间开销为O (nk+ )实际观察到的性能要好得多
