《优装载问题》PPT课件

1、最优装载问题姓名：谭立威学号：0301307371精选ppt简介问题描述实现原理贪心性质代码实现致谢2精选ppt问题描述有一批集装箱要装上一艘载重量为 c的轮船。第 i个集装箱的重量为 Wi。 最优装载问题要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。3精选ppt问题描述问题可形式化描述为：设：xi表示第i个集装箱是否装载， xi = 0 or 1, i = 1 to n; 求：Max(x1+x2+xn)约束条件：W1*x1 + W2*x2 + + Wn*xn = c4精选ppt实现原理每次选择时，从剩下的集装箱中，选择重量最小的集装箱。通过这样的选择可以保证已经选出来的集装箱总

2、重量最小，装载的集装箱数量最多，直到船只不能再继续装载为止。5精选ppt证明考虑任意装载容量为K的非空子问题Sk，令am是Sk中重量最小的集装箱，则am在Sk的某个集装箱装载数量最多且总重量最少的最优子集中。证明：令Ak是Sk的一个最优子集，且aj是Ak中重量最小的集装箱。若aj=am，则证明am在Sk的某个最优子集中。若ajam，则将Ak中的aj替换为am得到Ak，amweight (struct box*)b)-weight) return 1; else return 0;/按集装箱重量对集装箱进行快速排序 qsort(boxes,8,sizeof(struct box),cmp);时间

3、复杂度为O(n2)11精选ppt代码实现/累加重量 计算可装载集装箱数量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)12精选ppt代码实现编号为6，2，5，7，3，0的集装箱总重量为390单位且已被装载，剩余的装载容量

4、为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)13精选ppt代码实现截图14精选ppt致谢感谢刘东林老师给予这次讲课机会感谢邵舒迪同志的帮助Thanks for your attentions参考：算法导论第三版 十六章 定理16.1；互联网：/p-422844096.html ；15精选ppt代

5、码实现完整代码#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 flag

6、8 = 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(boxe

7、s,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);