已用箱子
下界
最少可能

      物品重量(kg)

        更多关于装箱问题

        装箱问题

        把货物装上货车、把文件存进磁盘、把任务分给机器:装箱问题问的是如何把一组物品放进尽可能少的同样大小的箱子。目前还没有已知的快速方法能总是找到最佳装法,但简单的规则已经相当接近。选一个规则,逐步执行,再和精确答案比较。 点按货架上的物品,再点按要放入的箱子:绿色的箱子放得下它,“新箱子”会再开一个箱子。点按箱子里的物品可以把它取出来。把所有物品装进尽可能少的箱子;下界(总重量除以箱子容量,向上取整)和最少可能的箱子数显示你离目标有多近,“最少箱子”显示最佳装法。在面板中修改物品的重量(以千克为单位)和箱子容量。“逐步”视图展示快速规则如何装箱:下次适应、首次适应或最佳适应,物品按输入顺序或从大到小排序;也可以查看动态规划求得的精确答案。按“播放”观看物品装进箱子,或按“单步”和“后退”一次走一步,拖动步骤滑块可跳到任意位置。选中装箱区时,方向键逐步前进或后退,空格键播放或暂停,Home 和 End 跳到开头和结尾。

        它是如何运作的

        1. 点按一件物品,再点按还有空间的箱子把它放进去,或点按“新箱子”再开一个箱子。
        2. 尽量少用箱子,或按“最少箱子”查看最佳装法。
        3. 打开“逐步”视图,选择一条规则并按播放,观看每件物品逐个尝试箱子。

        规则

        下次适应只让最后一个箱子保持打开:放不进去的物品就开一个新箱子。首次适应从第一个箱子开始尝试,选第一个放得下的箱子。最佳适应尝试所有箱子,选放得下的箱子中最满的那个,使剩余空间最少。首次适应和最佳适应还可以先把物品从大到小排序,这就是降序首次适应和降序最佳适应。

        精确答案

        最后一个规则不是经验法则:它通过对物品集合做动态规划找出最少的箱子数。对每个物品集合,它记录装下这些物品所需的最少箱子数,以及在箱子数相同的装法中最后一个箱子的最小装载量。集合每次增加一个物品,这个物品要么补进最后一个箱子,要么开一个新箱子。n 个物品有 2ⁿ 个集合,所以本应用最多允许 12 个物品。下界,即总大小除以箱子容量后向上取整,可以显示一种装法离最优有多近。

        常见问题

        哪种装箱规则最好?

        在快速规则中,降序首次适应和降序最佳适应最强:它们使用的箱子数永远不超过最少箱子数的 11/9 再加一个小常数。对未排序的物品,首次适应和最佳适应不超过最少箱子数的 1.7 倍,下次适应不超过 2 倍。

        为什么装箱问题很难?

        仅仅判断物品能否装进两个箱子,就已经是划分问题,而它是 NP 完全的。所以除非 P = NP,否则没有方法能对所有输入都快速找到最少的箱子数,精确方法在最坏情况下需要指数时间。

        什么是下界?

        物品的总大小除以箱子容量,再向上取整。任何装法都不可能用更少的箱子,因为这些箱子必须装下所有物品。最佳装法常常正好等于下界,但并非总是如此:三个大小为 6 的物品、箱子容量为 10 时,下界是 2,却需要 3 个箱子。

        这是动态规划吗?

        精确答案是:它利用较小集合的最佳装法,为每个物品集合构建最佳装法。快速规则则是贪心方法,一旦决定就不再回头。

        会向任何地方发送数据吗?

        不会。所有计算都在你的浏览器中完成,你上次的设置保存在这个浏览器的本地存储中。

        准备好尝试了吗?

        在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

        前往编辑器