2.2加勒比海盗船——最优装载问题
2.2.1问题解析2.2.2算法设计2.2.3完美图解2.2.5实战演练2.2.6 算法解析及优化拓展1.算法复杂度分析2.优化拓展在北美洲东南部，有一片神秘的海域，那里碧海蓝天、阳光明媚，这正式传说中海盗最活跃的加勒比海(Caribbean Sea)。17世纪时，这里更是欧洲大陆的商旅舰队到达美洲的必经之地，所以当时的海盗活动非常猖獗，海盗不仅攻击过往上人，甚至攻击英国皇家舰队……
有一天，海盗帽截获了一艘装满各种各样古董店货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为C，每件古董的重量为wi，海盗们该如何把尽可能多数量的宝贝装上海盗船呢？
2.2.1问题解析
根据问题描述可知这是一个可以用贪心算法求解答最优装载问题，要求装载的物品的数量尽可能多，而船的容量是固定的，那么优先把重量小的物品放进去，在容器固定的情况下，装的物品最多。采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而产生最优装载问题的最优解。
2.2.2算法设计
（1）当载重量为定值C时，wi越小时，可装载的古董数量n越大。只要依次选择最小重量古董，直到不能再装为止。
（2）把n个古董店重量从小到大(非递减)排序，然后根据贪心策略尽可能多地选出前i个古董，直到不能继续装为止，此时达到最优。
2.2.3完美图解
每个古董店重量如表2-1所示，海盗船的载重量C为30，那么在不打碎古董又不超过载重量的情况下，怎么装入最多的古董？
（1）因为贪心策略师每次选择重量最小的古董装入海盗船，因此可以按照古董重量递增排序，排序后如表2-2所示。
（2）按照贪心策略，每次选择重量最小的古董放入（设Sum代表宝物的重量，count代表已经装载的宝物数量
）
i=0，选择排序后的第1个，装入重量Sum=2，不超过载重量C=30,count=1
i=1，选择排序后的第2个，装入重量Sum=2+3=5，不超过载重量C=30,count=2
i=2，选择排序后的第3个，装入重量Sum=5+4=9，不超过载重量C=30,count=3
i=3，选择排序后的第4个，装入重量Sum=9+5=14，不超过载重量C=30,count=4
i=4，选择排序后的第5个，装入重量Sum=14+7=21，不超过载重量C=30,count=5
i=5，选择排序后的第6个，超过载重量C=30,算法结束
即放入古董的个数为count=5个。
# 2.2.4伪代码详解
2.2.5实战演练
weight, zong = map(float, input().split()) # 总载重量和总古董数list_gu = list(map(float, input().split())) # 存储每个古董的重量list_gu.sort() # 排序count = 0 # 可装古董数量Sum = 0 # 已装古董重量if zong == len(list_gu): # 保证输入的数据与zong匹配for i in list_gu:if Sum + i < weight: # 如果当前重量+下一件货物的重量 < weightSum += icount += 1else:breakprint(count)else:print(-1)
2.2.6 算法解析及优化拓展
1.算法复杂度分析
（1）时间复杂度：首先需要按古董重量排序，调用sort函数，其平均时间复杂度为O(n+nlog(n))，输入和贪心策略求解的for语句时间复杂度为O(n)，因此时间复杂度为O(b+nlog(n))。
（2）空间复杂度：程序中变量count、Sum等占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为O(1)。
2.优化拓展
如果想知道装入了哪些古董，需要添加什么程序来实现呢?还有没有更好的算法来解决这个问题？
weight, zong = map(float, input().split()) # 总载重量和总古董数list_gu = list(map(float, input().split())) # 存储每个古董的重量list_gu.sort() # 排序count = 0 # 可装古董数量Sum = 0 # 已装古董重量list_sum = []if zong == len(list_gu): # 保证输入的数据与zong匹配for i in list_gu:if Sum + i < weight:Sum += icount += 1list_sum.append(i)else:breakprint("总数量为:%d,总重量为%.2f" % (count, Sum))for i in list_sum:print(i, end=" ")else:print(-1)
