分享
 
 
 

1.3.2 0/1背包问题

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

在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 (x<1 0 0 ),使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点,考虑例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。贪婪算法结果为x=[1,0], 这种方案的值为1 0。对于y≥1 0 / 9,最优解的值为9 y。因此,贪婪算法的值与最优解的差对最优解的比例为( ( 9y - 1 0)/9y* 1 0 0 ) %,对于大的y,这个值趋近于1 0 0 %。但是可以建立贪婪启发式方法来提供解,使解的结果与最优解的值之差在最优值的x% (x<100) 之内。首先将最多k 件物品放入背包,如果这k 件物品重量大于c,则放弃它。否则,剩余的容量用来考虑将剩余物品按pi /wi 递减的顺序装入。通过考虑由启发法产生的解法中最多为k 件物品的所有可能的子集来得到最优解。

例13-9 考虑n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。当k= 0时,背包按物品价值密度非递减顺序装入,首先将物品1放入背包,然后是物品2,背包剩下的容量为5个单元,剩下的物品没有一个合适的,因此解为x = [ 1 , 1 , 0 , 0 ]。此解获得的价值为1 6。

现在考虑k = 1时的贪婪启发法。最初的子集为{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }产生与k= 0时相同的结果,考虑子集{ 3 },置x3 为1。此时还剩5个单位的容量,按价值密度非递增顺序来考虑如何利用这5个单位的容量。首先考虑物品1,它适合,因此取x1 为1,这时仅剩下3个单位容量了,且剩余物品没有能够加入背包中的物品。通过子集{ 3 }开始求解得结果为x = [ 1 , 0 , 1 , 0 ],获得的价值为1 8。若从子集{ 4 }开始,产生的解为x = [ 1 , 0 , 0 , 1 ],获得的价值为1 9。考虑子集大小为0和1时获得的最优解为[ 1 , 0 , 0 , 1 ]。这个解是通过k= 1的贪婪启发式算法得到的。

若k= 2,除了考虑k< 2的子集,还必需考虑子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。首先从最后一个子集开始,它是不可行的,故将其抛弃,剩下的子集经求解分别得到如下结果:[ 1 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ],这些结果中最后一个价值为2 3,它的值比k= 0和k= 1时获得的解要高,这个答案即为启发式方法产生的结果。 这种修改后的贪婪启发方法称为k阶优化方法(k - o p t i m a l)。也就是,若从答案中取出k 件物品,并放入另外k 件,获得的结果不会比原来的好,而且用这种方式获得的值在最优值的( 1 0 0 / (k + 1 ) ) %以内。当k= 1时,保证最终结果在最佳值的5 0 %以内;当k= 2时,则在3 3 . 3 3 %以内等等,这种启发式方法的执行时间随k 的增大而增加,需要测试的子集数目为O (nk ),每一个子集所需时间为O (n),因此当k >0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。

转载自沙大工作室

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有