下载掌阅APP，畅读海量书库
立即打开
有一天，海盗们截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了价值。虽然海盗船足够大，但载重为 c ，每件古董的重量为 w i ，海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船，该怎么办呢？
根据问题描述可知，这是一个可以用贪心算法求解的最优装载问题，要求装载的物品尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，在容量固定的情况下，装的物品最多。可以采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而得到最优装载问题的最优解。
（1）当载重为定值 c 时， w i 越小，可装载的古董数量 n 越大。依次选择最小重量的古董，直到不能装入为止。
（2）把 n 个古董的重量从小到大（非递减）排序，然后根据贪心策略尽可能多地选出前 i 个古董，直到不能继续装入为止。此时装入的古董数量就达到全局最优解。
每个古董的重量都如下表所示，海盗船的载重 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）个。
根据算法设计描述，可以用一维数组 w []存储古董的重量。
（1）按重量排序。可以利用C++中的排序函数sort，对古董的重量从小到大（非递减）排序。要使用此函数，只需引入头文件：#include <algorithm>。排序函数如下：
在本例中，只需要调用sort函数对古董的重量从小到大排序即可：sort( w , w + n )。
（2）按照贪心策略找最优解。首先用变量ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量，将两个变量都初始化为0；然后在按照重量从小到大排序的基础上，依次检查每个古董，使tmp加上该古董的重量，如果其结果小于或等于载重 c ，则令ans++；否则退出。
时间复杂度 ：按古董重量排序并调用sort函数，其平均时间复杂度为 O ( n log n )，输入和贪心策略求解的两个for语句的时间复杂度均为 O ( n )，因此总时间复杂度为 O ( n log n )。
空间复杂度 ：在程序中使用了tmp、ans等辅助变量，空间复杂度为 O (1)。