资源描述：
《最优装载问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最优装载问题姓名：谭立威学号：030130737简介问题描述实现原理贪心性质代码实现致谢问题描述有一批集装箱要装上一艘载重量为c的轮船。第i个集装箱的重量为Wi。最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。问题描述问题可形式化描述为：设：xi表示第i个集装箱是否装载，xi=0or1,i=1ton;求：Max(x1+x2+…+xn)约束条件：W1*x1+W2*x2+…+Wn*xn<=c实现原理每次选择时，从剩下的集装箱中，选择重量最小的集装箱。通过这样的选择可以保证已经选出来的集装箱总重量最小，装载的集装箱数量最多，直到船只不能再继续装载为止。证明考虑任意装载容量为K
2、的非空子问题Sk，令am是Sk中重量最小的集装箱，则am在Sk的某个集装箱装载数量最多且总重量最少的最优子集中。证明：令Ak是Sk的一个最优子集，且aj是Ak中重量最小的集装箱。若aj=am，则证明am在Sk的某个最优子集中。若aj≠am，则将Ak中的aj替换为am得到Ak’，am<=aj。由于
3、Ak’
4、=
5、Ak
6、，所以Ak’也是Sk的一个集装箱装载数量最多的的最优子集，且它包含am。贪心性质通过上述证明我们可以知道，每次比较计算得到最小的集装箱，它在最优解中，选出来之后，对余下的集装箱（子问题）采取同样的策略选取最轻的集装箱，放入最优解当中，得到局部最优解，这样逐步缩小问题规模即缩小剩余载重
7、量。最终得到全局最优解。代码实现系统环境：Win7操作系统开发平台：DEV-C++4.9.9.1代码实现问题实例假设集装箱数量n=8,八个集装箱的重量是[W0,W2,…,W7]=[100,200,50,90,150,50,20,80],船只载重c=400。求该条件下的最优装载问题。代码实现—数据结构//集装箱结构体typedefstructbox{intweight;//重量intindex;//初始序号};代码实现//比较子函数intcmp(constvoid*a,constvoid*b){if(((structbox*)a)->weight>((structbox*)b)->weight)
8、return1;elsereturn0;}//按集装箱重量对集装箱进行快速排序qsort(boxes,8,sizeof(structbox),cmp);时间复杂度为O(n2)代码实现//累加重量计算可装载集装箱数量maxLoad=500;countLoad=0;quantity=0;for(i=0;i<8;i++){//如果还能继续装载if(boxes[i].weight<=maxLoad-countLoad){countLoad=countLoad+boxes[i].weight;//计算最大装载数量quantityquantity++;//获取装载标记flag[boxes[i].index
9、]=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=0to7总的时间复杂度为O(n2)+c*O(n)，即O(n2)([W0,W2,…,W7]=[100,200,50,90,150,50,20,80],船只载重c=400)代码实现—截图致谢感谢刘东林老师给予这次讲课机会感谢邵舒迪同志的帮助Thanksforyourattentions参考：《算法导论》
10、第三版十六章定理16.1；互联网：http://www.docin.com/p-422844096.html；代码实现—完整代码#include#include//集装箱结构体}typedefstructbox{intweight;//重量intindex;//初始序号};//比较子函数intcmp(constvoid*a,constvoid*b){if(((structbox*)a)->weight>((structbox*)b)->weight)return1;elsereturn0;intmain(){//初始化集装箱集合structboxboxes
11、[8]={100,0,200,0,50,0,90,0,150,0,50,0,20,0,80,0};intflag[8]={0};//集装箱装载标志inti;intquantity;//可装载集装箱数量intmaxLoad;//船只最大载重intcountLoad;//已经装载重量//输出集装箱初始数据printf("集装箱初始数据");printf("");for(i=0;i<8;i++){p
