如果你是加勒比海盗首领，会选择哪种算法来使价值最大化？

喜欢电影的人可能看过《加勒比海盗》这部电影，在电影中每个海盗都想获得无尽的财宝。

我们假设一种场景，一伙海盗在岛上发现了一个沙矿，这座沙矿可以生产三种沙子：沙子 A、沙子 B 和沙子 C。

三种沙子有不同的质量和价值，沙子 B 质量最大，价值也最高，沙子 C 质量最小，价值也最低，沙子 A 的价值和质量在沙子 B 和沙子 C 之间。

海盗的小船有承重限制，所有沙子的质量已经超过小船承重的极限，超过承重极限船就会浮不起来，所以不可能把所有沙子都装到船上。

如果你是这伙海盗的首领，你想在不沉船的情况下，获得总价值最高的沙子，你会怎么装载呢？

01 如何装沙子赚更多的钱你是这伙海盗的首领，带着大家辛辛苦苦、冒着生命的危险来到这座小岛上，找到了可以带来财富的沙子。但是，你也不知道怎么用小船装沙子才能赚更多的钱，这时候你在内部开了一个会议集思广益，看看手下人有没有好的想法。海盗甲：老大，我们首先应该选择质量最小的沙子 C 装到船上，装完沙子 C 以后，再把质量次小的沙子 A 装到船上，最后用沙子 B 装满小船，这样岛上只剩下沙子 B 啦，沙子 A 和沙子 C 都被我们装完了，赚的钱应该最多。

海盗乙第一个站起来反对：老大，我觉得海盗甲说的不对，我们应该先装价值最高的沙子 B，装完沙子 B 以后，再装价值次高的沙子 A，直到小船装满，这样岛上只剩下价值最低的沙子 C，价值最高的沙子 A 和沙子 B 都被我们装上船了，赚的钱肯定比海盗甲的方案多。

海盗丙推了推眼镜，轻轻说道：老大，他俩说的都不对，海盗甲只考虑了质量，没有考虑沙子的价值，海盗乙只考虑了沙子的价值，没有考虑沙子的质量，我认为选择沙子应该既考虑质量又考虑价值，我们应该首先选择单位价值最高的沙子，然后选择单位价值次高的沙子，这样赚的钱才会是最多的。

听了三个小弟的建议，你也不知道谁的建议才是最正确的，看着手下人都在等着你决定怎么搬沙子，你才发现做海盗还是要有知识、懂算法才行。

海盗丙看出了你的心思，又推了推眼镜说道：老大，不要担心，你先听听我的分析，再来做决定。

02 海盗的智慧海盗丙推了推眼镜继续说道：在这座小岛上，一共就有三种沙子，分别是沙子 A、沙子 B 和沙子 C，其质量分别是 20、30、10，对应的价值分别为 60、120、50，沙子 B 虽然价值最高，但是质量也最大，沙子 C 质量最小，价值也最低。我们的小船可以装沙子的质量是 50。因为沙子的种类也不是很多，我们直接分析就好了。

下面我们按照海盗甲的思路来进行装载。

（1）因为小船的承重是 50，首先我们把质量最小的沙子 C 全部装到船上，沙子 C 的全部质量是 10，装完沙子 C 以后，小船还能装载质量为 40 的沙子；

（2）然后把质量次小的沙子 A 全部装到船上，沙子 A 的全部质量是 20，装完沙子 A 以后，小船还能承重 20；

（3）最后用沙子 B 装满小船，沙子 B 的总质量是 30，装满小船以后，小岛上还剩下质量为 10 的沙子 B，海盗甲的装载策略如图 1 所示。

图 1 海盗甲的装载策略

通过海盗甲的方案，我们装在船上的沙子价值多少呢？

船上沙子 C 的价值为 50，沙子 A 的价值为 60，沙子 B 总质量是 30，船上只装了 20，所以船上沙子 B 的价值是 80。因此，按照海盗甲的方案，船上沙子的总价值是 190。

接下来我们按照海盗乙的策略来进行装载。

（1）因为小船的承重是 50，首先我们把价值最高的沙子 B 全部装到船上，沙子 B 的全部质量是 30，装完沙子 B 以后，小船还能装载质量为 20 的沙子；

（2）然后把价值次高的沙子 A 全部装到船上，沙子 A 的全部质量是 20，装完沙子 A 以后，小船也装满了；

（3）因为小船装满了，价值最低的沙子 C 一丁点也没有装上船，海盗乙的装载策略如图 2 所示。

图 2 海盗乙的装载策略

通过海盗乙的方案，我们装在船上的沙子价值多少呢？

沙子 B 全部装上了船，所以沙子 B 总的价值为 120，沙子 A 也全部装上了船，所以沙子 A 总的价值为 60。

因此，按照海盗乙的方案，船上沙子的总价值是 180，比海盗甲的方案还少了 10。

最后我们按照海盗丙的思路来进行装载。

海盗丙的装载思路是按照单位价值最高的沙子进行依次装载，沙子 A 的总质量是 20，总价值是 60，所以单位价值是 3；沙子 B 的总质量是 30，总价值是 120，所以单位价值是 4；沙子 C 的总质量是 10，总价值是 50，所以单位价值是 5。按照单位价值进行贪心，首先装载沙子 C，然后装载沙子 B，最后装载沙子 A。

（1）因为小船的承重是 50，首先我们把单位价值最高的沙子 C 全部装到船上，沙子 C 的全部质量是 10，装完沙子 C 以后，小船还能装载质量为 40 的沙子；

（2）然后把单位价值次高的沙子 B 全部装到船上，沙子 B 的全部质量是 30，装完沙子 B 以后，小船还能装载质量为 10 的沙子；

（3）最后用沙子 A 装满小船，沙子 A 的总质量是 20，装完小船以后，小岛上还剩下质量为 10 的沙子 A，海盗丙的装载策略如图 3 所示。

图 3 海盗丙的装载策略

通过海盗丙的方案，我们装在船上的沙子价值多少呢？

沙子 C 全部装上了船，所以沙子 C 总的价值为 50，沙子 B 也全部装上了船，所以沙子 B 总的价值为 120，沙子 A 总质量是 20，船上只装了 10，所以船上沙子 A 的价值是 30。

因此，按照海盗丙的方案，船上沙子的总价值是 200，价值比海盗甲和海盗乙的方案都高一些。

海盗丙骄傲地对老大说：老大，三个方案都分析完了，海盗甲的方案价值是 190，海盗乙的方案价值是 180，我的方案价值是 200，选哪个方案一目了然了吧！

听了海盗丙的分析，你满意地点点头，决定就按照海盗丙的方案来进行装船，这一次海盗收获颇丰。收获颇丰的基础还是要学会分析，否则按照海盗甲或者海盗乙的方案装船，将损失一笔价值不菲的财富。

03 背包问题算法实现通过上一节的图解，相信大家对背包问题算法已经有了了解，背包问题算法的实质就是对单位价值最高的物品进行贪心，那么接下来我们进行实战编程。

我们通过程序帮助海盗找到最高价值的装载方案，小岛的三种沙子：沙子 A、沙子 B 和沙子 C，质量分别是 20、30、10，对应的总价值分别为 60、120、50。小船最多能装质量为 50 的沙子。算法完整代码如下。

#货物类 class Goods(object):def init(self,name=None,weight=None,price=None):#货物名字 self._name = name#货物质量 self._weight = weight ;#货物总价格 self._price = price

#背包问题 class Knapsack(object):def init(self,capacity,goods_list):self._capacity = capacityself._good_list = goods_list

def greed(self,goods):    result = []    for good in goods:        #如果是能放得下的物品，就全部放下        if(good._weight < self._capacity):            self._capacity = self._capacity - good._weight            result.append(good)        else:            #如果物品不能完全放下，则考虑放入部分物品            result.append(Goods(good._name,self._capacity,self._capacity * good._price/good._weight))            break    return result
#按照权重排序def weight(self):    goods = [Goods(part[0],part[1],part[2]) for part in self._good_list]    goods.sort(key=lambda x:x._weight,reverse=False)    return self.greed(goods)
#按照总价值排序def price(self):    goods = [Goods(part[0],part[1],part[2]) for part in self._good_list]    goods.sort(key=lambda x:x._price,reverse=True)    return self.greed(goods)
#按照单位价值排序def density(self):    goods = [Goods(part[0], part[1], part[2]) for part in self._good_list]    goods.sort(key=lambda x: x._price/x._weight, reverse=True)    return self.greed(goods)

if name == "main":knapsack = Knapsack(50,[('沙子 A',20,60),('沙子 B',30,120),('沙子 C',10,50)])goods = knapsack.weight()total_price = 0 ;for good in goods:total_price = total_price + good._priceprint("海盗甲：基于沙子质量贪心方案是：%d" % total_price)

knapsack = Knapsack(50, [('沙子A', 20, 60), ('沙子B', 30, 120), ('沙子C', 10, 50)])goods = knapsack.price()total_price = 0;for good in goods:    total_price = total_price + good._priceprint("海盗乙：基于沙子总价值贪心方案是：%d" % total_price)
knapsack = Knapsack(50, [('沙子A', 20, 60), ('沙子B', 30, 120), ('沙子C', 10, 50)])goods = knapsack.density()total_price = 0;for good in goods:    total_price = total_price + good._priceprint("海盗丙：基于沙子单位价值贪心方案是：%d" % total_price)

背包问题算法程序运行结果如图 4 所示。

图 4 背包问题算法程序运行结果

可以发现，程序的运行结果和前面的分析结果是一致的。我们已经成功地帮助海盗们找到了最佳的装载方案，海盗们高高兴兴地装船去啦。接下来我们对程序重要的数据结构和方法进行讲解。

首先我们要定义一个货物类，该货物类应该包含如下信息：货物名字、货物质量、货物总价值，如下所示。

#货物类 class Goods(object):def init(self,name=None,weight=None,price=None):#货物名字 self._name = name#货物质量 self._weight = weight ;#货物总价值 self._price = price 算法中我们定义了三个方案，分别是海盗甲的基于质量贪心、海盗乙的基于总价值贪心及海盗丙的基于单位价值贪心。

海盗甲的基于质量贪心方法如下所示。

#按照质量排序def weight(self):    goods = [Goods(part[0],part[1],part[2]) for part in self._good_list]    goods.sort(key=lambda x:x._weight,reverse=False)    return self.greed(goods)

海盗乙的基于总价值贪心方法如下所示。

#按照总价值排序def price(self):    goods = [Goods(part[0],part[1],part[2]) for part in self._good_list]    goods.sort(key=lambda x:x._price,reverse=True)    return self.greed(goods)

最后是海盗丙的基于单位价值贪心方法如下所示。

def density(self):goods = [Goods(part[0], part[1], part[2]) for part in self._good_list]goods.sort(key=lambda x: x._price/x._weight, reverse=True)return self.greed(goods)

本文摘自《从零开始学算法（基于 Python）》一书！

想要通过更多有趣的故事来了解算法吗？

欢迎阅读本书！

▊《从零开始学算法（基于 Python）》

李峰 著

内容全面：涵盖程序员需要掌握的 7 种类别算法

化繁为简：列举 30 个趣味故事，提升阅读乐趣

实例驱动：每个算法都配有 Python 实例，即学即练

本书的目的是帮助初学者掌握编程中的基础算法，并通过 Python 语言进行实战演练，通过即学即练的方式掌握这些经典算法，让读者真正体会算法的美妙，成为读者学习算法的领路人。

本书分为 8 章，涵盖的主要内容有：算法之美，通过生活中的例子学习算法；贪心算法，选择当前最优的方案；分而治之算法，将复杂的问题拆分为简单的问题；树算法，围绕树结构的各种算法；图算法，围绕图结构的各种算法；动态规划，一种求解最优问题的强大工具；回溯法，深度优先遍历问题的解空间；分支限界法，广度优先遍历问题的解空间。

本书内容通俗易懂，案例丰富，实用性强，适合算法初学者阅读，也适合 Python 程序员及其他编程爱好者阅读。另外，本书也适合作为相关培训机构的教材。