如果你是加勒比海盗首领，会选择哪种算法来使价值最大化？
👆点击“博文视点Broadview”，获取更多书讯
喜欢电影的人可能看过《加勒比海盗》这部电影，在电影中每个海盗都想获得无尽的财宝。
我们假设一种场景，一伙海盗在岛上发现了一个沙矿，这座沙矿可以生产三种沙子：沙子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 = capacity self._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._price print("海盗甲：基于沙子质量贪心方案是：%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._price print("海盗乙：基于沙子总价值贪心方案是：%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._price print("海盗丙：基于沙子单位价值贪心方案是：%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程序员及其他编程爱好者阅读。另外，本书也适合作为相关培训机构的教材
（扫码了解本书详情！）
热文推荐