下载掌阅APP，畅读海量书库
立即打开
2.5 搬家师傅的烦恼
|
|
喜欢电视剧的人可能看过《蜗居》这部电视剧，在该电视剧中有各种各样的搬家场景。搬过家的人应该深有体会，搬家是非常累的。在实际生活中，我们搬家通常会先预订搬家师傅，然后把家里的物品打包，最后搬上车。现在假设一个场景，你预订的搬家师傅的车容量有点小，不能把所有的物品装上车，需要多次运送。但是打包的物品都已经用了好几年了，其价值可能还抵不上运费钱，你希望在运送的时候尽可能多地把物品装到车上，只送一次，剩下的直接扔掉。你要怎样装载，才能将尽可能多的物品装上车呢？
老王刚买了一个新房，需要将现在住的房子的物品搬到新房子里，老王忙了一早上，连水都没来得及喝，终于把所有的物品打包好了。望着眼前大大小小的包裹，老王满意地点了点头。接下来就是预订搬家师傅了，半个小时后，搬家师傅来了，看了一下眼前的包裹。
师傅对老王说：“这些物品一趟可能装不完，需要多运几趟，运费要加钱。”
老王一听要加钱，看了看眼前用了好几年的东西，也不值几个钱，还抵不上多出来的一趟运费。
老王缓缓说道：“一趟就好，剩下的直接扔掉就可以了，但是你要保证这一趟要把尽可能多的物品装到车上。”
师傅自信满满地说道：“好嘞，我干了十年搬家工作了，这点要求对我来说还是没有问题的，您就瞧好吧！”
老王打包的物品也没有多少，一共才打包了8个物品，8个物品的体积分别如下：
● 物品A：4；
● 物品B：1；
● 物品C：3；
● 物品D：2；
● 物品E：7；
● 物品F：12；
● 物品G：11；
● 物品H：7。
而搬家师傅的装载车容量是20。只见搬家师傅想都没想，看了一眼眼前的8个物品，撸起袖子，干起活来。
（1）搬家师傅先把体积最小的物品B装到了车上。搬家车的容量是20，B的体积是1，所以搬家车的容量还剩19，如图2.31所示。
（2）然后搬家师傅把剩下物品中体积最小的物品D装到了车上。搬家车的剩余容量是19，D的体积是2，所以搬家车的容量还剩17，如图2.32所示。
（3）接着搬家师傅把剩下物品中体积最小的物品C装到了车上。搬家车的剩余容量是17，C的体积是3，所以搬家车的容量还剩14，如图2.33所示。
图2.31 基于容量进行贪心装载物品B
图2.32 基于容量进行贪心装载物品D
图2.33 基于容量进行贪心装载物品C
（4）再然后搬家师傅把剩下物品中体积最小的物品A装到了车上。搬家车的剩余容量是14，A的体积是4，所以搬家车的容量还剩10，如图2.34所示。
图2.34 基于容量进行贪心装载物品A
（5）最后搬家师傅把剩下物品中体积最小的物品E装到了车上。搬家车的剩余容量是10，E的体积是7，所以搬家车的容量还剩3，如图2.35所示。
图2.35 基于容量进行贪心装载物品E
搬家师傅看了看搬家车剩余的容量和没有装载的物品，擦了擦额头上的汗水，说道：“老板，装完了，你看一下”。
老王看了看装载的物品，满意地点了点头。老王是个程序员，他对搬家师傅的搬物品策略进行了分析，每次都是选剩余物品中体积最小的物品进行装载，其本质就是基于物品的体积进行贪心，从而保证装载车可以装载最多的物品。搬家师傅虽然不懂什么贪心算法，但是十年的搬家经验使得他无意间使用了该算法，老王默默嘀咕着：算法来源于生活，生活中处处都是算法呀。
通过上一节的图解，相信大家对装载问题算法已经有了了解，装载问题算法的实质就是对体积最小的物品进行贪心，老王是个算法爱好者，知道搬家师傅是根据经验进行装载的，并没有理论基础，如果是个没有经验的小伙子搬家可能会搬错。接下来老王要通过编程模拟装载策略，来指导没有经验的小伙子搬家。算法完整代码如下。
装载问题算法程序运行结果如图2.36所示。
图2.36 装载问题算法程序运行结果
可以发现，程序的运行结果和前面的分析结果是一致的。老王已经成功地通过程序模拟了装载策略，这样，如果来的搬家师傅没有经验，也可以通过程序帮助没有经验的搬家师傅装载物品。接下来我们对程序重要的数据结构和方法进行讲解。
首先我们要定义一个包裹类，该包裹类应该包含如下信息：包裹名字、包裹质量，如下所示。
在算法中我们会对物品的体积从小到大进行排序，如下所示。
每次将体积最小的物品装到搬家车上，直到搬家车装不了为止，如下所示。
