《优装载问题》PPT课件.ppt

《《优装载问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《优装载问题》PPT课件.ppt（16页珍藏版）》请在三一办公上搜索。

1、最优装载问题,姓名：谭立威学号：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,实现原理,每次选择时，从剩下的集装箱中，选择重量最小的集装箱。通过这样的选择可以保证已经选出来的集装箱总重量最小，装载的集装箱数量最多，直到船只不能再继续装载为止。,

2、证明,考虑任意装载容量为K的非空子问题Sk，令am是Sk中重量最小的集装箱，则am在Sk的某个集装箱装载数量最多且总重量最少的最优子集中。证明：令Ak是Sk的一个最优子集，且aj是Ak中重量最小的集装箱。若aj=am，则证明am在Sk的某个最优子集中。若ajam，则将Ak中的aj替换为am得到Ak，am=aj。由于|Ak|=|Ak|，所以Ak也是Sk的一个集装箱装载数量最多的的最优子集，且它包含am。,贪心性质,通过上述证明我们可以知道，每次比较计算得到最小的集装箱，它在最优解中，选出来之后，对余下的集装箱（子问题）采取同样的策略选取最轻的集装箱，放入最优解当中，得到局部最优解，这样逐步缩小问

3、题规模即缩小剩余载重量。最终得到全局最优解。,代码实现,系统环境：Win7操作系统开发平台：,代码实现,问题实例 假设集装箱数量n=8,八个集装箱的重量是 W0,W2,W7=100,200,50,90,150,50,20,80,船只载重c=400。求该条件下的最优装载问题。,代码实现数据结构,/集装箱 结构体 typedef struct box int weight;/重量 int index;/初始序号;,代码实现,/比较子函数 int cmp(const void*a,const void*b)if(struct box*)a)-weight(struct box*)b)-weight)

4、return 1;else return 0;/按集装箱重量对集装箱进行快速排序 qsort(boxes,8,sizeof(struct box),cmp);时间复杂度为O(n2),代码实现,/累加重量 计算可装载集装箱数量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;时间复杂度

5、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(n2)+c*O(n)，即O(n2)(W0,W2,W7=100,200,50,90,150,50,20,80,船只载重c=400),代码实现截图,致谢,感谢刘东林老师给予这次讲课机会感谢邵舒迪同志的帮助Thanks for your attentions参考：算法导论第三版 十六章 定理16.1；互

6、联网：；,代码实现完整代码,#include#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;/集装箱装载标

7、志 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);/

8、从小到达输出集装箱重量 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();,