资源描述:
《贪婪算法---0-1背包问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、贪婪算法---0-1背包问题背包问题在0/1背包问题中,需对容量为c的背包进行装载。从n个物品中选取装入背包的物品,每件物品i的重量为wi,价值为pi。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高,即n?i=1pixi取得最大值。约束条件为n?i=1wixi≤c和xi?[0,1](1≤i≤n)。在这个表达式中,需求出xt的值。xi=1表示物品i装入背包中,xi=0表示物品i不装入背包。0/1背包问题是一个一般化的货箱装载问题,即每个货箱所获得的价值不同。货箱装载问题转化为背包问题
2、的形式为:船作为背包,货箱作为可装入背包的物品。例1-8在杂货店比赛中你获得了第一名,奖品是一车免费杂货。店中有n种不同的货物。规则规定从每种货物中最多只能拿一件,车子的容量为c,物品i需占用wi的空间,价值为pi。你的目标是使车中装载的物品价值最大。当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。这个问题可仿照0/1背包问题进行建模,其中车对应于背包,货物对应于物品。0/1背包问题有好几种贪婪策略,每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为:从剩余的
3、物品中,选出可以装入背包的价值最大的物品,利用这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,考虑n=2,w=[100,10,10],p=[20,15,15],c=105。当利用价值贪婪准则时,获得的解为x=[1,0,0],这种方案的总价值为20。而最优解为[0,1,1],其总价值为30。另一种方案是重量贪婪准则是:从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解,但在一般情况下则不一定能得到最优解。考虑n=
4、2,w=[10,20],p=[5,100],c=25。当利用重量贪婪策略时,获得的解为x=[1,0],比最优解[0,1]要差。还可以利用另一方案,价值密度pi/wi贪婪算法,这种选择准则为:从剩余物品中选择可装入包的pi/wi值最大的物品,这种策略也不能保证得到最优解。利用此策略试解n=3,w=[20,15,15],p=[40,25,25],c=30时的最优解。我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧,0/1背包问题是一个NP-复杂问题。对于这类问题,也许根本就不可能找到具有多项式时间的算法。虽然按pi/wi
5、非递(增)减的次序装入物品不能保证得到最优解,但它是一个直觉上近似的解。我们希望它是一个好的启发式算法,且大多数时候能很好地接近最后算法。在600个随机产生的背包问题中,用这种启发式贪婪算法来解有239题为最优解。有583个例子与最优解相差10%,所有600个答案与最优解之差全在25%以内。该算法能在O(nlogn)时间内获得如此好的性能。我们也许会问,是否存在一个x(x<100),使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点,考虑例子n=2,w=[1,y],p=[10,9y],和c=y。贪婪算法结
6、果为x=[1,0],这种方案的值为10。对于y≥10/9,最优解的值为9y。因此,贪婪算法的值与最优解的差对最优解的比例为((9y-10)/9y*100)%,对于大的y,这个值趋近于100%。但是可以建立贪婪启发式方法来提供解,使解的结果与最优解的值之差在最优值的x%(x<100)之内。首先将最多k件物品放入背包,如果这k件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按pi/wi递减的顺序装入。通过考虑由启发法产生的解法中最多为k件物品的所有可能的子集来得到最优解。例13-9考虑n=4,w=[2,4,6,7]
7、,p=[6,10,12,13],c=11。当k=0时,背包按物品价值密度非递减顺序装入,首先将物品1放入背包,然后是物品2,背包剩下的容量为5个单元,剩下的物品没有一个合适的,因此解为x=[1,1,0,0]。此解获得的价值为16。现在考虑k=1时的贪婪启发法。最初的子集为{1},{2},{3},{4}。子集{1},{2}产生与k=0时相同的结果,考虑子集{3},置x3为1。此时还剩5个单位的容量,按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1,它适合,因此取x1为1,这时仅剩下3个单位容量了,且剩余物品没
8、有能够加入背包中的物品。通过子集{3}开始求解得结果为x=[1,0,1,0],获得的价值为18。若从子集{4}开始,产生的解为x=[1,0,0,1],获得的价值为19。考虑子集大小为0和1时获得的最优解为[1,0,0,1]。这个解是通过k=1的贪婪启发式算法得到的。若k=2,除了考虑k<2