装箱问题
搬家时,你一个接一个地装满纸箱,不禁会想:换个更聪明的顺序,是不是能少用几个?这就是装箱问题,它以难著称:即使是计算机,对于大规模输入也只能靠巧妙的搜索才能找到最少的箱子数。不过,简单的规则却出奇地接近最优。
问题
给定一些有大小的物品,以及容量都相同的箱子,把每个物品放进一个箱子,不让任何箱子溢出,并且用的箱子尽可能少。大小可以代表重量、长度、时长或文件大小。它听起来像是雨天午后的消遣谜题,但它是 NP 困难的:目前还没有已知的方法能对所有输入都快速找到最少的箱子数。
快速规则
下次适应一直装一个箱子,直到下一个物品放不进去,然后开一个新箱子,再也不回头。首次适应让所有箱子都保持打开,把每个物品放进第一个放得下的箱子。最佳适应把每个物品放进仍放得下的最满的箱子。这三种规则都是立即决定的,当物品一个一个到来并且必须马上放好时,这很有用。
先排序
难放的是大物品,因为它们需要很多空余空间。先把物品从大到小排序,再用首次适应或最佳适应,就能趁箱子还空着时放入大物品,再用小物品填补空隙。降序首次适应使用的箱子数永远不超过最少箱子数的 11/9 再加一个常数,而对未排序物品使用首次适应则是 1.7 倍。
一个例子
取容量为 10 的箱子,以及物品 2、3、2、1、3、4、5、6、7 和 7,总和为 40。首次适应把 2、3、2 和 1 放进第一个箱子,把 3 和 4 放进第二个,然后 5、6、7 和 7 各需要一个箱子:共 6 个箱子。从大到小排序后,降序首次适应得到 7 + 3、7 + 3、6 + 4 和 5 + 2 + 2 + 1:4 个装满的箱子,正好等于下界 40 / 10 = 4。
求最少箱子数
物品不多时,可以用子集动态规划求出精确答案:对每个物品集合,求出装下它的最少箱子数和最空的最后一个箱子,并由少一个物品的集合逐步推出。对 n 个物品,这大约需要 2ⁿ·n 步。更大的实例用分支定界或整数规划求解,而下界可以说明一种装法离最优最多差多远。
用在哪里
装载卡车和集装箱、从标准长度的管材或纸卷中切割并尽量减少浪费(下料问题)、把虚拟机分配到服务器上、把文件存到磁盘上,这些都是装箱问题。在二维和三维中,用盒子代替数字,问题就更难了。
常见问题
在线装箱和离线装箱有什么区别?
在线时,每个物品一到就必须放好,而不知道后面还有什么;下次适应、首次适应和最佳适应就是这样工作的。离线时,所有物品事先都已知道,所以可以先排序,就像降序首次适应那样。
降序首次适应能有多接近最优?
它最多使用最少箱子数的 11/9 再加 6/9 个箱子,György Dósa 在 2007 年证明了这个界是紧的。在典型输入上,它通常是最优的,或者只多一个箱子。
装箱问题和背包问题一样吗?
两者相关但不同。背包问题是用最有价值的物品装满一个背包;装箱问题是把所有物品放进尽可能少的背包。精确的装箱求解器常常通过一遍又一遍地求解类似背包的问题来工作。
为什么本应用最多只允许 12 个物品?
因为精确答案要查看每一个物品集合,而 12 个物品就已经有 4096 个集合。快速规则可以处理成千上万个物品,但绘图以及与精确答案的比较就做不到了。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试装箱