主題
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) 中。

另請參閱

切餅乾問題, 鋪磚問題

使用 探索

參考文獻

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.

在 中引用

裝箱問題

請引用為

Weisstein, Eric W. "裝箱問題。" 來自 —— 資源。 https://mathworld.tw/Bin-PackingProblem.html

主題分類