最优装载问题-数据结构与算法Java版

1.问题描述

有一批集装箱要装上一艘载重量为C的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。

2.问题分析

分析最优装载问题能否可用贪心算法求解，也就是看该问题是否满足贪心算法解决问题的两个特征。

（1）贪心选择性质，也就是按贪心选择策略最终能够得到问题最优解的性质。

本问题的最优解是最终装载最多集装箱，而采用的贪心选择策略是“最轻的先装”策略。下面用反证法来说明该问题是满足贪心选择性质的。将集装箱按照重量从小到大排序，设（x1,x2,…,xn）为其最优解（其中，xi取值{0，1}）。若该最优解不为贪心选择所得，比如设第一个装载的集装箱为k号集装箱，不是原第1个集装箱，即x1=0,xk=1，则采取另一种方案（y1,…,yi,…,yn），其中y1=1，yk=0，yi=xi，则仍为最优解，同理，将最优解中装载的重的货物换成轻的，仍满足重量和小于C的条件。所以，贪心选择可以得到最优解，问题满足贪心选择性质。

（2）最优子结构性质，也就是问题的最优解包含其子问题的最优解。

本问题是要求出重量小于C时装载最多集装箱，而子问题就是在已经装了部分集装箱后，重量小于j时装载最多集装箱。同样用反证法说明，如果最优解（x1,…,xn）中不包含子问题的最优解（xi,…,xn），则设子问题最优解为（yi,…,yn），其中在重量j下装载了更多的集装箱，则用其替换（xi,…,xn），得到（x1,…,yi,…,yn），比原解更优，与原最优解（x1,…,xn）矛盾。所以，原问题最优解包含子问题最优解，问题满足最优子结构性质。(www.xing528.com)

3.解决问题

最终，最优装载问题由“最轻者先装”的贪心选择策略来解决，步骤如下。

步骤1：将集装箱按重量排序。

步骤2：从第一个集装箱开始，若该集装箱重量小于船的剩余载重量，则装入，循环步骤2；若船的剩余载重量不能装下该集装箱，则解题完成。

具体算法程序如下：

在实现该排序过程时，原重量数组是不变的，只按照重量从小到大将其下标排序。算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlog2n)。