- 高级算法和数据结构
- (意)马塞洛·拉·罗卡
- 4230字
- 2024-01-31 17:45:16
1.3 打包背包：数据结构与现实世界的结合
恭喜，你被选中为火星定居点的首个居民！不过，火星上并没有商店，不能随便购物。鉴于这种情况，你只能自己种植农作物以获取食物。但是，在最初的几个月里，你可以依靠随身携带的食物来维持自己的生命。
1.3.1 抽象化问题
不过，你能携带的食物有这样一个问题：货运箱的总重量不能超过1000kg，这是一个硬性限制。
更麻烦的是，你只能从下面这组已经打包在盒子里的食物中进行选择。
● 土豆，800kg。
● 大米，300kg。
● 面粉，400kg。
● 花生酱，20kg。
● 番茄罐头，300kg。
● 豆类，300kg。
● 草莓酱，50kg。
水是不限量的，但是对于上面的每一种食物，你只能选择要不要带，而不能拆分并重新打包。显然，你不会只带土豆（就像《火星救援》里那样），而是会对要放进货运箱里的东西有所选择。
对于探险队来说，他们期望你在逗留期间能够保持良好的身体状态和充沛的精力。因此，要带什么食物的主要选择标准是食物的营养价值。如果用食物的总热量（总卡路里，1卡路里 = 4.19焦耳）来表示其营养价值，那么每一种可带食物的总卡路里如表1.1所示。
表1.1 每一种可带食物的重量及其总卡路里[6]
[6] 为便于计算，对于食物的总热量，本书保留了总卡路里（单位：卡，1卡 = 4.19焦耳）这一说法。——编辑注。
实际上，你的选择并不能改变实际可以携带的食物（尽管你的抗议可以理解，但任务控制部门在这一点上绝不会让步），真正重要的是每个盒子的重量及其所能提供的总卡路里。
我们的问题可以抽象为：“在不能对任何元素进行分割的情况下，从一个集合中选择任意数量的元素，使得它们的总重量不超过1 000kg并且提供的热量最高。”
1.3.2 寻找解决方案
问题已经明确了，接下来我们就可以开始寻找解决方案了。
装箱的一种方式是，优先选择内有总卡路里最高的食物的盒子，也就是重达800kg的一整盒土豆。
但是，这样做会导致大米和面粉无法被放进货运箱，而且它们两者的总卡路里远远超过你可以在剩余的200kg内放进的其他任何食物组合。按照这种策略，你可以获得的最高热量是1 749 400卡路里（选择土豆、草莓酱和花生酱）。
因此，看起来最自然的策略——贪心算法（greedy algorithm）[7]，会在每个步骤里选择目前最优的选项——并不能带来最好的结果。为了得到更好的答案，你需要再仔细考虑一下这个问题。
[7] 贪心算法是解决问题的一种策略，通过在每个步骤里做出局部最优选择来尝试找到最优解。贪心算法虽然只能针对一小类问题找到最佳解决方案，但是也可被用来作为获得近似（次优）解决方案的启发式算法。
是时候集思广益了。为此，你召集了整个物流团队一起寻找解决方案。
很快，有人建议应该查看每千克食物的平均卡路里而不是一整盒食物的总卡路里。于是，你为表1.1新添加了一列，并基于这一列中的值进行了相应的排序，如表1.2所示。
表1.2 将表1.1按照每千克食物的平均卡路里进行排序的结果
接下来，我们可以试着从上至下挑选单位重量卡路里最高的食物，最后得到包含花生酱、大米、面粉和草莓酱的组合——总共能提供2 813 800卡路里。
这比第一个结果要好很多。但是，稍加注意你就能发现，在选择花生酱之后，我们就不能再带上豆类了；而如果携带豆类的话，则还能进一步增加货运箱里食品的总热量。不过，至少你不用再被迫接受《火星救援》里的食物了，因为这次火星上没有土豆。
在进行若干小时的集思广益之后，你打算放弃寻找更好的解决方案了。你发现要解决这个问题，得到更优解决方案的唯一办法就是逐一检查每种食物以确定要不要携带。唯一能做到这一点的方法就是枚举出所有可能的解决方案，并剔除超出重量阈值的解决方案，然后从剩下的解决方案中挑选出最好的那个。这就是所谓的暴力（brute force）算法，是一种代价非常高昂的算法。
对于每种食物，你都可以选择是携带还是留下，因此可能的解决方案有27 = 128种。显然，你并不太愿意逐一尝试这100多种解决方案。几小时之后，你已经筋疲力尽，但也理解了为什么这种算法被称为暴力算法，并且至少解决了这个问题。
然后消息传开了。在收到一些未来定居者的投诉之后，任务控制部门打来了电话，告诉你清单里会额外增加25种新的食物，包括糖、橙子、大豆和马麦酱等。
看完你给出的计算组合，所有人都倍感沮丧，因为现在有大约40亿种不同的组合需要尝试。
1.3.3 拯救大家的算法
显然，这时你需要一个计算机程序来帮助你实施计算，以得出最佳决策。
你会在接下来的几小时内编写相关的代码。但是，即使用上了计算机程序，你也需要花费很长的时间（若干小时）才能得到结果。紧接着，你发现自己的算法需要假设所有定居者的饮食习惯相同，但是实际上，其中的一部分人对某些食物过敏。比如，有25%的人不能吃麸质食物，还有更多的人声明他们对马麦酱过敏。因此，你必须根据不同人的过敏情况分别运行这个算法若干次。更糟的是，任务控制部门为了让有过敏反应的人也能吃得足够丰富，正在考虑为食品清单额外添加30种食物。如果真的决定了要这样做，那么我们最终会有62种食物可选，所编写的程序将不得不遍历超过数十亿种可能的组合。你尝试运行了一下这个程序，发现一天之后这个程序仍在运行，并且离得到结果还很远。
团队打算放弃找到最佳组合，回到吃土豆这个方案。这时，有人想起发射团队中某个人的桌子上有一本算法书。
你给发射团队打了电话，他们马上反馈这是一个0-1背包问题。坏消息是，0-1背包问题属于NP完全问题[8]，从而意味着这个问题很难解决，因为不会有“很快速的”（能在多项式时间内完成的）算法能计算出这个问题的最优解。
[8] NP完全（NP-complete）问题是这样一组问题，它们的任何解都可以被快速（在多项式时间内）验证，但尚不存在有效的方法能找到这个解。根据定义，NP完全问题无法在经典的确定型机器（例如我们将在第2章中定义的RAM模型）上，在多项式时间内得到答案。
不过好消息是，对于0-1背包问题，有一个伪多项式[9]解决方案。这是一种使用动态编程（dynamic programming）的解决方案[10]，所要花费的时间与背包的最大容量成正比。更好的办法是让货运箱的容量变得有限，于是这个解决方案需要执行的步骤数量就等于可能的填充容量乘以食物种类的数量。因此，假设最小单位是1kg，那么只需要执行1000 × 62步，就能得到答案了。这相比262这个数要好太多了！在重写算法之后，新算法在几秒内就能找到最佳解决方案。
[9] 对于伪多项式算法，最坏情况下的运行时间（多项式时间）还取决于输入的值，而不仅仅取决于输入的大小。例如，对于0-1背包问题，输入是n个元素（重量和值的组合），背包的容量为C。多项式算法的复杂度仅由元素的数量n决定，而伪多项式算法的复杂度还取决于（或者仅取决于）背包的容量C。
[10] 动态编程是一种解决具有某种特征的复杂问题的策略。这种特性是指，要计算出最终解决方案，就需要对子问题进行多次递归调用。这种策略会通过把问题分解为更简单的子问题的集合来得到最终解决方案，并且这些子问题的解决方案会被保存起来，从而保证只被计算或解决一次。
于是，你可以把这个算法当作一个黑盒，直接把它插入程序中而不用再关心更多的细节。但是，这一决择与你的职业发展密切相关，因此你还是应该对这个算法的工作原理进行更深入的了解。
对于最初的例子来说，明显可以找到的最佳组合是大米、面粉和豆类，总计3 256 000卡路里。与第一次尝试相比，这已经是一个非常好的结果了！
最初的例子其实很简单（只有7种食物），因此你可能直接猜到了最佳组合。如果是这样的话，你可以试着计算在面对更接近实际情况的上百种不同的食物时，需要多少年才能手动找到最佳解决方案！
这个解决方案已经很不错了，因为在各种限制下，这已经是我们能够找到的最佳解决方案了。
1.3.4 打破常规来思考问题
但是，真正的算法专家会怎么做呢？假设在准备环节，恰好有一位专家在航天基地访问，并且受邀帮助我们计算节省燃料的最佳路线。午休时，有人非常自豪地告诉专家你们如何出色地解决了打包食物的问题。专家随后问道：“为什么不把盒子拆开呢？”
答案可能是“从来没有拆开过盒子”，或是“这些食物在供应商那里已经打包好了，重新打包需要花费更多的时间和金钱”。
接下来，这位专家就会解释道：“如果我们可以把包装盒拆开，那么0-1背包问题（属于NP完全问题）就会变成无限制背包问题。通常来说，无限制背包问题的线性时间[11]的贪婪解决方案，甚至都要比0-1背包问题的最佳解决方案更好一些。”
[11] 线性时间需要假设食物列表是有序的，否则就会产生线性对数时间的复杂度。
简单来说，我们可以把这个问题转换为其他更容易解决的问题，从而使得打包在货运箱里的食物能提供尽可能多的卡路里。于是，问题就变成了“在可以对元素进行分割的情况下，从一个集合中选择任意数量的元素，使得它们的总重量不超过1000千克并且提供的热量最高。”
再者说，即使需要更多的花销来重新打包所有食物也是值得的，因为这样做能得到更好的结果。
具体来说，如果可以选择打包各种食物的一部分，就可以简单地从卡路里含量最高的食物（在本例中为花生酱）开始打包。当发现不能把一个盒子里的所有食物都打包进去时，只需要打包其中一部分以填满整个货运箱就行了。因此，最终重新打包所有食物甚至都不是必需的，只需重新打包一种食物就行了。
于是，最佳解决方案是打包花生酱、大米、面粉、草莓酱和230kg的豆类，共计3 342 800卡路里。
1.3.5 完美的结局
未来的火星定居者能够维持生存的能力还是不错的，也不会因为只吃土豆、花生酱和草莓酱而沮丧了。
从计算的角度看，我们从不正确的算法（采用最高总数和最高比例的贪婪解决方案），过渡到了正确但不可行的算法（枚举出所有可能组合的暴力解决方案），最后得到了一种非常灵活且更高效的解决方案。
同样重要甚至更重要的是，我们打破了常规来思考这个问题。我们通过删除一些约束条件简化了问题，进而找到一种更简单的算法和更好的解决方案。这个过程实际上是一条黄金法则，即“持续彻底地研究需求，思考是否需要它们，并且在可能的情况下尝试删除它们。”这些可能的情况包括：删除这些需求能够带来价值至少相同的解决方案，或者可以用更低的成本实现价值稍低的解决方案。当然在这个过程中，也有一些必须考虑的其他方面的问题（例如各个层面的法律和安全性），因此某些约束条件是不能删除的。
如前所述，在描述算法的过程中，接下来要做的是详细描述这个解决方案并给出实现方法的指南。
这里我们省略了0-1背包问题的动态规划算法的具体步骤。原因是：首先，这是一种算法，而不是数据结构；其次，这种算法在大量文献里都有相应的描述；最后，我们在本章中提到它，只是为了说明避免选择使用错误的算法和数据结构是多么重要，以及概述在第2章中介绍问题及其解决方案时所要遵循的过程。