填充體積算法

我有一些尺寸長度，寬度，高度的框。填充體積算法

我有不同長度，寬度，高度的項目。

是否有一個現有的算法，可以確定最好的項目用於放入箱子？

2011-08-08 pdiddy

包裝盒問題的揹包問題？ –

這是TCO的Maraton Match問題之一，如果你在TCO註冊，你可以找到一個很好的解決方案（我不知道什麼時候，但我認爲一年前）。非解決方案是準確的答案，他們都嘗試使用模擬退火，並像這樣。 –

這叫做包裝/切割庫存/揹包問題，它很難。一般來說，你只能獲得使用啓發式的近似解，例如參見

2011-08-08 20:45:47

這不是他們。你能解釋一下它的近似值嗎？ –

所有這些算法都可以幫助您優化無界空間，至少在一維空間中。需要的是從給定有限的盒子尺寸的可用項目中選擇最佳擬合。 –

它可能完全匹配他們中的任何一個。但他們都緊密相關。例如。一個箱子的箱子包裝成爲另一個問題。在文獻中，這種問題通常被稱爲「三維包裝問題」。學者搜索提供了相當多的結果http://scholar.google.com/scholar?q=box+packing+problem –

這也許並不是真正的答案，但我相信答案是這個問題是無法回答的。是的，這是一個包裝問題的版本。但是看看Erich Friedma在2維空間中的研究：看來等方矩形的問題仍然沒有解決 - 看看這些解決方案的複雜性！

（問題是造成略有不同，即如何最好地安排一定數量的項目佔用最小的空間，而不是選擇哪些項目，但我希望你的問題減少了迭代這種計算在對象的幾種組合）

和3- d變體，它看起來非常僅部分地解決： http://www2.stetson.edu/~efriedma/cubincub/

大概你最好的選擇是安德斯建議的啓發式，儘管幾乎肯定會對幾乎所有問題都不是最理想的。有趣的是，最優化的解決方案似乎是非常不規則的，所以你可能不會找到它們。

2011-08-09 00:32:32

回答