最优装载问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最优装载问题,姓名：谭立威,学号：,030130737,简介,问题描述,实现原理,贪心性质,代码实现,致谢,问题描述,有一批集装箱要装上一艘载重量为,c,的轮船。第,i,个集装箱的重量为,Wi,。,最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。,问题描述,问题可形式化描述为：,设：,xi,表示第,i,个集装箱是否装载，,xi=0 or 1,i=1 to n;,求：,Max(x1+x2+,xn,),约束条件：,W1*x1+W2*x2+,Wn,*,xn,=c,实现原理,每次选择时，从剩下的集装箱中，选择重量最小的集装箱。通过这样的选择可以保证已经选出来的集装箱总重量最小，装载的集装箱数量最多，直到船只不能再继续装载为止。,证明,考虑任意装载容量为,K,的非空子问题,S,k,，令,a,m,是,S,k,中重量最小的集装箱，则,a,m,在,S,k,的某个集装箱装载数量最多且总重量最少的最优子集中。,证明：令,A,k,是,S,k,的一个最优子集，且,a,j,是,A,k,中重量最小的集装箱。若,a,j,=a,m,，则证明,a,m,在,S,k,的某个最优子集中。若,a,j,a,m,，则将,A,k,中的,a,j,替换为,a,m,得到,A,k,，,a,m,weight (,struct,box*)b)-weight),return 1;,else,return 0;,/,按集装箱重量对集装箱进行快速排序,qsort(boxes,8,sizeof(struct,box),cmp,);,时间复杂度为,O(n,2,),代码实现,/,累加重量,计算可装载集装箱数量,maxLoad,=500;,countLoad,=0;,quantity=0;,for(i,=0;i8;i+),/,如果还能继续装载,if(boxesi.weight,=,maxLoad,-,countLoad,),countLoad,=,countLoad,+,boxesi.weight,;,/,计算最大装载数量quantity,quantity+;,/,获取装载标记,flagboxesi.index,=1;,时间复杂度,O(n,),代码实现,编号为,6,，,2,，,5,，,7,，,3,，,0,的集装箱总重量为,390,单位且已被装载，剩余的装载容量为,10,个单位，小于剩余任一集装箱的重量。问题结束。在这个贪心解决算法中通过,flag,数组中的结果可以得到,x0,x1,x7=1,0,1,1,0,1,1,1,，且,xi=6,i=0 to 7,总的时间复杂度为,O(n,2,)+c*,O(n,),，即,O(n,2,),(W0,W2,W7=100,200,50,90,150,50,20,80,船只载重,c=400),代码实现,截图,致谢,感谢刘东林老师给予这次讲课机会,感谢邵舒迪同志的帮助,Thanks for,your,attentions,参考：,算法导论,第三版 十六章 定理,16.1,；,互联网：,#include,/,集装箱,结构体,typedef,struct,box,int,weight;/,重量,int,index;/,初始序号,;,/,比较子函数,int,cmp,(const void*a,const void*b),if(struct,box*)a)-weight (,struct,box*)b)-weight),return 1;,else,return 0;,int,main(),/,初始化集装箱集合,struct,box boxes8=100,0,200,0,50,0,90,0,150,0,50,0,20,0,80,0;,int,flag8=0;/集装箱装载标志,int,i;,int,quantity;/,可装载集装箱数量,int,maxLoad,;/,船只最大载重,int,countLoad;/已经装载重量,/,输出集装箱初始数据,printf(集装箱初始数据,);,printf(n,);,for(i,=0;i8;i+),printf(b%d:%d,t,i,boxesi.weight,);,printf(n,);,/,初始化,集装箱序号,for(i,=0;i8;i+),boxesi.index,=i;,printf(n,);,printf(快速排序之后,：);,printf(n,);,/,按集装箱重量对集装箱进行快速排序,qsort(boxes,8,sizeof(struct,box),cmp,);,/,从小到达输出集装箱重量,for(i,=0;i8;i+),printf(b%d:%d,t,i,boxesi.weight,);,printf(n,);,printf(n,);,printf(集装箱初始时的下标,:);,printf(n,);,/,输出集装箱初始时的下标,for(i,=0;i8;i+),printf(index%d:%d,t,i,boxesi.index,);,printf(n,);,/,累加重量,计算可装载集装箱数量,maxLoad,=500;,countLoad,=0;,quantity=0;,for(i,=0;i8;i+),/,如果还能继续装载,if(boxesi.weight,=,maxLoad,-,countLoad,),countLoad,=,countLoad,+,boxesi.weight,;,/,计算最大装载数量quantity,quantity+;,/,获取装载标记,flagboxesi.index,=1;,printf(n,);,printf(集装箱最大装载数,：);,printf(n,);,printf(quantity:%d,quantity,);,printf(n,);,printf(n,);,printf(集装箱装载标志,：);,printf(n,);,/,输出集装箱装载标志,for(i,=0;i8;i+),printf(flag%d:%d,t,i,flagi,);,/,屏幕显示,暂停,return(,int)getchar,();,