主题
Search

装箱问题

将一组物品装入若干个箱子中的问题，使得总重量、体积等不超过某个最大值。一种简单的算法（首次适应算法）按照物品到来的顺序，将它们放入第一个适合的箱子中。1973年，J. Ullman 证明了这种算法与最优装箱的差异可能高达 70% (Hoffman 1998, p. 171)。另一种策略首先将物品从大到小排序，然后按顺序将它们放入第一个适合的箱子中。1973年，D. Johnson 表明，这种策略的次优程度永远不会超过 22%，而且没有任何有效的装箱算法能保证做得比 22% 更好 (Hoffman 1998, p. 172)。

存在一些物品排列，使得在移除一个物品后应用装箱算法，比包含该物品时需要更多一个箱子 (Hoffman 1998, pp. 172-173)。Sylvia Halasz 构建了第一个这样的例子，并发表在 Graham (1976, pp. 223 和 225, 图 5.46) 中。

另请参阅

切饼干问题, 铺砖问题

使用 Wolfram|Alpha 探索

参考文献

Albers, S. 和 Mitzenmacher, M. "First Fit 和 Random Fit 装箱的平均情况分析。" Random Structures Alg. 16, 240-259, 2000.Coffman, E. G. Jr.; Garey, M. R.; 和 Johnson, D. S. "装箱近似算法——更新的综述。" 收录于 计算机系统设计的算法设计。 Vienna: Springer-Verlag, pp. 49-106, 1984.Garey, M. R.; Graham, R. L.; 和 Ullman, J. D. "一些装箱算法的分析。" 收录于 组合算法。 New York: Algorithmics Press, pp. 39-47, 1973.Graham, R. L. "调度算法性能的界限。" 收录于 计算机和作业车间调度理论 (Ed. E. G. Coffman Jr.). New York: Wiley, pp. 165-227, 1976.Johnson, D. S. "组合问题的近似算法。" 收录于 J. Comput. System Sci. 9, 256-278, 1974.Johnson, D. S. "组合问题的近似算法。" 收录于 第五届 ACM 计算理论研讨会（Austin, Tex., 1973）。 New York: Assoc. Comput. Mach., pp. 38-49, 1973.Hoffman, P. The Man Who Loved Only Numbers: 保罗·埃尔德什和寻找数学真理的故事。 New York: Hyperion, 1998.

在 Wolfram|Alpha 中引用

装箱问题

请引用为

Weisstein, Eric W. "装箱问题。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/Bin-PackingProblem.html

主题分类