这个问题来自例 船可以分步装载每步装一个货箱且需要考虑装载哪一个货箱根据这种思想可利用如下贪婪准则从剩下的货箱中选择重量最小的货箱这种选择次序可以保证所选的货箱总重量最小从而可以装载更多的货箱根据这种贪婪策略首先选择最轻的货箱然后选次轻的货箱如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱
例 假设n = [w w ]=[] c= 利用贪婪算法时所考察货箱的顺序为 货箱 的总重量为 个单位且已被装载剩下的装载能力为 个单位小于剩下的任何一个货箱在这种贪婪解决算法中得到[x x ] = [ ]且?xi =
定理 利用贪婪算法能产生最佳装载
证明可以采用如下方式来证明贪婪算法的最优性令x = [x xn ]为用贪婪算法获得的解令y =[ y yn ]为任意一个可行解只需证明n ?i= xi ≥n ?i= yi 不失一般性可以假设货箱都排好了序即wi≤wi + (≤i≤n)然后分几步将y 转化为x转换过程中每一步都产生一个可行的新y且n ?i = yi 大于等于未转化前的值最后便可证明n ?i = xi ≥n ?j = yi
根据贪婪算法的工作过程可知在[ n] 的范围内有一个k使得xi = i≤k且xi = i>k寻找[ n]范围内最小的整数j使得xj≠yj 若没有这样的j 存在则n ?i= xi =n ?i = yi 如果有这样的j 存在则j≤k否则y 就不是一个可行解因为xj≠yj xj = 且yj = 令yj = 若结果得到的y 不是可行解则在[ j+ n]范围内必有一个l 使得yl = 令yl = 由于wj≤wl 则得到的y 是可行的而且得到的新y 至少与原来的y 具有相同数目的
经过数次这种转化可将y 转化为x由于每次转化产生的新y 至少与前一个y 具有相同数目的因此x 至少与初始的y 具有相同的数目货箱装载算法的C + +代码实现见程序 由于贪婪算法按货箱重量递增的顺序装载程序 首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序(见 节间接寻址的定义)随后货箱便可按重量递增的顺序装载由于间接寻址排序所需的时间为O (nl o gn)(也可利用 节的堆排序及第章的归并排序)算法其余部分所需时间为O (n)因此程序 的总的复杂性为O (nl o gn)
程序 货箱装船
template
void ContainerLoading(int x[] T w[] T c int n)
{// 货箱装船问题的贪婪算法
// x[i] = 当且仅当货箱i被装载 <=i<=n
// c是船的容量 w 是货箱的重量
// 对重量按间接寻址方式排序
// t 是间接寻址表
int *t = new int [n+];
I n d i r e c t S o r t ( w t n);
// 此时 w[t[i]] <= w[t[i+]] <=i < p>
// 初始化x
for (int i = ; i <= n; i++)
x[i] = ;
// 按重量次序选择物品
for (i = ; i <= n && w[t[i]] <= c; i++) {
x[t[i]] = ;
c = w[t[i]];} // 剩余容量
delete [] t;
}
