最优装载问题ppt课件

1、简介,问题描述 实现原理 贪心性质 代码实现 致谢,问题描述,有一批集装箱要装上一艘载重量为 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操作系统 开发平台： DEV-C+ 4.9.9.1,代码实现,问题实例 假设集装箱数量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 (

4、struct box*)b)-weight) 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; 时间复杂度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,代码实现截图,致谢,感谢刘东林老师给予