2.4.3 背包问题算法实现

通过上一节的图解，相信大家对背包问题算法已经有了了解，背包问题算法的实质就是对单位价值最高的物品进行贪心，那么接下来我们进行实战编程。我们通过程序帮助海盗找到最高价值的装载方案，小岛的三种沙子：沙子A、沙子B和沙子C，质量分别是20、30、10，对应的总价值分别为60、120、50。小船最多能装质量为50的沙子。算法完整代码如下。

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

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

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

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

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

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

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