【原创：李峰】

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

我们假设一种场景，一伙海盗在岛上发现了一个沙矿，这座沙矿可以生产三种沙子：沙子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的沙子。算法完整代码如下。



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

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

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

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

算法中我们定义了三个方案，分别是海盗甲的基于质量贪心、海盗乙的基于总价值贪心及海盗丙的基于单位价值贪心。

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

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

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

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

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

欢迎阅读本书！

《从零开始学算法（基于Python）》
李峰 著

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

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

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

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

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

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

（扫码了解本书详情！）