《贪婪算法---货箱装船》由会员分享，可在线阅读，更多相关《贪婪算法---货箱装船（2页珍藏版）》请在金锄头文库上搜索。
1、贪婪算法-货箱装船.txt 我的人生有 A 面也有 B 面，你的人生有 S 面也有 B 面。 失败不 可怕，关键看是不是成功他妈。现在的大学生太没素质了！过来拷毛片，居然用剪切！有空 学风水去，死后占个好墓也算弥补了生前买不起好房的遗憾。货箱装船这个问题来自例 1 - 2。船可以分步装载，每步装一个货箱，且需要考虑装载哪一个货箱。 根据这种思想可利用如下贪婪准则：从剩下的货箱中，选择重量最小的货箱。这种选择次序 可以保证所选的货箱总重量最小，从而可以装载更多的货箱。根据这种贪婪策略，首先选择 最轻的货箱，然后选次轻的货箱，如此下去直到所有货箱均装上船或船上不能再容纳其他任 何一个货箱。 例 1
2、-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
3、 , ., xn 为用贪婪算法获 得的解，令 y = y1 , ., yn 为任意一个可行解，只需证明 n ?i= 1xi n ?i= 1yi 。 不失一般性，可以假设货箱都排好了序：即 wiwi + 1（1in） 。然后分几步将 y 转化 为 x，转换过程中每一步都产生一个可行的新 y，且 n ?i = 1yi 大于等于未转化前的值， 最后便可证明 n ?i = 1xi n ?j = 1yi 。根据贪婪算法的工作过程，可知在0, n 的范围内有一个 k，使得 xi =1, ik 且 xi =0, ik。寻找 1 ,n范围内最小的整数 j，使得 xjyj 。若没有这样的 j 存在，则 n ?i
4、= 1xi =n ?i = 1yi 。如果有这样的 j 存在，则 jk，否则 y 就不是一个可行解，因为 xjyj ，xj = 1 且 yj = 0。令 yj = 1，若结果得到的 y 不是可行解，则在 j+ 1 ,n范 围内必有一个 l 使得 yl = 1。令 yl = 0，由于 wjwl ，则得到的 y 是可行的。而且，得 到的新 y 至少与原来的 y 具有相同数目的 1。经过数次这种转化，可将 y 转化为 x。由于每次转化产生的新 y 至少与前一个 y 具有相同 数目的 1，因此 x 至少与初始的 y 具有相同的数目 1。货箱装载算法的 C + +代码实现见程 序 1 3 - 1。由于贪
5、婪算法按货箱重量递增的顺序装载，程序 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 货箱装船templatevoid ContainerLoading(int x, T w, T c, int n)/ 货箱装船问题的贪婪算法/ xi = 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);/ 此时, wti = wti+1, 1=i / 初始化 xfor (int i = 1; i = n; i+)xi = 0;/ 按重量次序选择物品for (i = 1; i = n i+) xti = 1;c -= wti; / 剩余容量delete t;
