分享
 
 
 

1.3.1 货箱装船

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

这个问题来自例1 - 2。船可以分步装载,每步装一个货箱,且需要考虑装载哪一个货箱。根据这种思想可利用如下贪婪准则:从剩下的货箱中,选择重量最小的货箱。这种选择次序可以保证所选的货箱总重量最小,从而可以装载更多的货箱。根据这种贪婪策略,首先选择最轻的货箱,然后选次轻的货箱,如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。

例1-7 假设n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用贪婪算法时,所考察货箱的顺序为7 , 3 , 6 , 8 , 4 , 1 , 5 , 2。货箱7 , 3 , 6 , 8 , 4 , 1的总重量为3 9 0个单位且已被装载,剩下的装载能力为1 0个单位,小于剩下的任何一个货箱。在这种贪婪解决算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且?xi = 6。

定理1-1 利用贪婪算法能产生最佳装载。

证明可以采用如下方式来证明贪婪算法的最优性:令x = [x1 , ..., xn ]为用贪婪算法获得的解,令y =[ y1 , ..., yn ]为任意一个可行解,只需证明n ?i= 1xi ≥n ?i= 1yi 。不失一般性,可以假设货箱都排好了序:即wi≤wi + 1(1≤i≤n)。然后分几步将y 转化为x,转换过程中每一步都产生一个可行的新y,且n ?i = 1yi 大于等于未转化前的值,最后便可证明n ?i = 1xi ≥n ?j = 1yi 。

根据贪婪算法的工作过程,可知在[0, n] 的范围内有一个k,使得xi =1, i≤k且xi =0, i>k。寻找[ 1 ,n]范围内最小的整数j,使得xj≠yj 。若没有这样的j 存在,则n ?i= 1xi =n ?i = 1yi 。如果有这样的j 存在,则j≤k,否则y 就不是一个可行解,因为xj≠yj ,xj = 1且yj = 0。令yj = 1,若结果得到的y 不是可行解,则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0,由于wj≤wl ,则得到的y 是可行的。而且,得到的新y 至少与原来的y 具有相同数目的1。

经过数次这种转化,可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1,因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载,程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序(见3 . 5节间接寻址的定义),随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)(也可利用9 . 5 . 1节的堆排序及第2章的归并排序),算法其余部分所需时间为O (n),因此程序1 3 - 1的总的复杂性为O (nl o gn)。

程序13-1 货箱装船

template

void ContainerLoading(int x[], T w[], T c, int n)

{// 货箱装船问题的贪婪算法

// x[i] = 1 当且仅当货箱i被装载, 1<=i<=n

// c是船的容量, w 是货箱的重量

// 对重量按间接寻址方式排序

// t 是间接寻址表

int *t = new int [n+1];

I n d i r e c t S o r t ( w, t, n);

// 此时, w[t[i]] <= w[t[i+1]], 1<=i

// 初始化x

for (int i = 1; i <= n; i++)

x[i] = 0;

// 按重量次序选择物品

for (i = 1; i <= n && w[t[i]] <= c; i++) {

x[t[i]] = 1;

c -= w[t[i]];} // 剩余容量

delete [] t;

}

转载自沙大工作室

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
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- 王朝網路 版權所有