最优装载问题 文档资料.pptVIP

最优装载问题 姓名：谭立威 学号： 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 =a j 。由于 |A k | = |A k | ，所 以 A k 也是 S k 的一个集装箱装载数量最多的的 最优子集，且它包含 a m 。 贪心性质 ? 通过上述证明我们可以知道，每次比较计算得 到最小的集装箱，它在最优解中，选出来之后， 对余下的集装箱（子问题）采取同样的策略选 取最轻的集装箱，放入最优解当中，得到局部 最优解，这样逐步缩小问题规模即缩小剩余载 重量。最终得到全局最优解。 代码实现 系统环境： 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 ((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(boxes[i].weight = maxLoad - countLoad){ countLoad = countLoad + boxes[i].weight; // 计算最大装载数量 quantity quantity ++; // 获取装载标记 flag[boxes[i].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 ? 总