数据结构(背包问题)假设有一个能装入总
在0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即n ?i=1pi xi 取得最大值。 约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中,需求出xt 的值。xi = 1表示物品i 装入背包中,xi =0 表示物品i 不装入背包。 0 / 1背包问题是一个一般化的货箱装载问题,即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为:船作为背包,货箱作为可装...全部
在0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即n ?i=1pi xi 取得最大值。
约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中,需求出xt 的值。xi = 1表示物品i 装入背包中,xi =0 表示物品i 不装入背包。
0 / 1背包问题是一个一般化的货箱装载问题,即每个货箱所获得的价值不同。货箱装载问题转化为背包问题的形式为:船作为背包,货箱作为可装入背包的物品。例1-8 在杂货店比赛中你获得了第一名,奖品是一车免费杂货。
店中有n 种不同的货物。规则规定从每种货物中最多只能拿一件,车子的容量为c,物品i 需占用wi 的空间,价值为pi 。你的目标是使车中装载的物品价值最大。当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。
这个问题可仿照0 / 1背包问题进行建模,其中车对应于背包,货物对应于物品。
0 / 1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。
一种贪婪准则为:从剩余的物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。
例如,考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。当利用价值贪婪准则时,获得的解为x= [ 1 , 0 , 0 ],这种方案的总价值为2 0。
而最优解为[ 0 , 1 , 1 ],其总价值为3 0。
另一种方案是重量贪婪准则是:从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。
考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时,获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
还可以利用另一方案,价值密度pi /wi 贪婪算法,这种选择准则为:从剩余物品中选择可
装入包的pi /wi 值最大的物品,这种策略也不能保证得到最优解。
利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。
我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧, 0 / 1背包问题是一个N P-复杂问题。
对于这类问题,也许根本就不可能找到具有多项式时间的算法。虽然按pi /wi 非递(增)减的次序装入物品不能保证得到最优解,但它是一个直觉上近似的解。我们希望它是一个好的启发式算法,且大多数时候能很好地接近最后算法。
在6 0 0个随机产生的背包问题中,用这种启发式贪婪算法来解有2 3 9题为最优解。有5 8 3个例子与最优解相差1 0 %,所有6 0 0个答案与最优解之差全在2 5 %以内。该算法能在O (nl o gn)时间内获得如此好的性能。
我们也许会问,是否存在一个x (x0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。收起