购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.2.2 最优装载问题

有一天,海盗们截获了一艘装满各种各样古董的货船,每件古董都价值连城,一旦打碎就失去了价值。虽然海盗船足够大,但载重为 c ,每件古董的重量为 w i ,海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船,该怎么办呢?

1. 问题分析

根据问题描述可知,这是一个可以用贪心算法求解的最优装载问题,要求装载的物品尽可能多,而船的容量是固定的,那么优先把重量小的物品放进去,在容量固定的情况下,装的物品最多。可以采用重量最轻者先装的贪心选择策略,从局部最优达到全局最优,从而得到最优装载问题的最优解。

2. 算法设计

(1)当载重为定值 c 时, w i 越小,可装载的古董数量 n 越大。依次选择最小重量的古董,直到不能装入为止。

(2)把 n 个古董的重量从小到大(非递减)排序,然后根据贪心策略尽可能多地选出前 i 个古董,直到不能继续装入为止。此时装入的古董数量就达到全局最优解。

3. 完美图解

每个古董的重量都如下表所示,海盗船的载重 c 为30,那么在不打碎古董又不超过载重的情况下,怎样装入最多的古董?

因为贪心策略是每次都选择重量最小的古董装入海盗船,因此可以按照古董的重量非递减排序,排序后如下表所示。

按照贪心策略,每次都选择重量最小的古董装入。

i =0:选择排序后的第1个古董装入,装入重量tmp=2,不超过载重30,ans=1。

i =1:选择排序后的第2个古董装入,装入重量tmp=2+3=5,不超过载重30,ans=2。

i =2:选择排序后的第3个古董装入,装入重量tmp=5+4=9,不超过载重30,ans=3。

i =3:选择排序后的第4个古董装入,装入重量tmp=9+5=14,不超过载重30,ans=4。

i =4:选择排序后的第5个古董装入,装入重量tmp=14+7=21,不超过载重30,ans=5。

i =5:选择排序后的第6个古董装入,装入重量tmp=21+10=31,超过载重30,算法结束。

即装入古董的个数为5(ans=5)个。

4. 算法实现

根据算法设计描述,可以用一维数组 w []存储古董的重量。

(1)按重量排序。可以利用C++中的排序函数sort,对古董的重量从小到大(非递减)排序。要使用此函数,只需引入头文件:#include <algorithm>。排序函数如下:

在本例中,只需要调用sort函数对古董的重量从小到大排序即可:sort( w , w + n )。

(2)按照贪心策略找最优解。首先用变量ans记录已经装载的古董个数,tmp代表装载到船上的古董的重量,将两个变量都初始化为0;然后在按照重量从小到大排序的基础上,依次检查每个古董,使tmp加上该古董的重量,如果其结果小于或等于载重 c ,则令ans++;否则退出。

5. 算法分析

时间复杂度 :按古董重量排序并调用sort函数,其平均时间复杂度为 O ( n log n ),输入和贪心策略求解的两个for语句的时间复杂度均为 O ( n ),因此总时间复杂度为 O ( n log n )。

空间复杂度 :在程序中使用了tmp、ans等辅助变量,空间复杂度为 O (1)。 /fupkN6L7pemcyATa/qSQk8Hef7bzr8qkpK3GdzR3im/vpGBaW08om5q8mGDujXR

点击中间区域
呼出菜单
上一章
目录
下一章
×