c语言算法 – 贪婪算法 – 货箱装船

这个问题来自例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;
}