爲一組三維矩形物品尋找最佳3D箱子尺寸

當我說箱子時，我正在討論裝運箱子。爲一組三維矩形物品尋找最佳3D箱子尺寸

我有一些隨機大小的小物品，我需要裝入儘可能少的盒子。我需要知道哪些箱子尺寸是最佳的。

所有項目都是rectangular prisms。
很容易排除太大而不適合的物品的箱子尺寸。
我知道箱子尺寸（它們是我現有的可用箱子尺寸）
項目可以水平或垂直放置，而不是對角線。
可以使用任意數量的箱子。目標是儘可能使用盡可能少的盒子。
可以使用多個箱子尺寸來最佳地適應不同尺寸的物品。

有什麼算法可以讓我計算出我需要用來獲得最佳空間使用的盒子大小？ 儘量將最多的物品放入儘可能少的盒子中。

可用的箱子尺寸來自我現有的庫存量。出於示例目的，您可以創建有限數量的組合框大小。

來源

2012-04-11 unixman83

那麼這隻涉及2個維度？長度和寬度？ – 2012-04-11 20:51:27

這聽起來與'NP-Complete'的'Knapsack'類似。你可以看看算法來估計'揹包'，看看你是否能夠適應你的需求。 – twain249 2012-04-11 20:52:39

@FrancisP立方體，長度，寬度和高度。我不知道立體矩形的*技術*詞。 – unixman83 2012-04-11 20:52:46

這是Bin packing problem的推廣，這意味着它是NP-Hard。

想要看到這一點，想象所有的垃圾桶和包具有相同的寬度和高度，而且所有垃圾箱（但不是包裝）的長度都相同。然後它是一個單維問題：我們有大小爲V的容器，並且包裝的大小爲，a ，...，a _n。這個簡化的案例正是Bin裝箱問題。因此，快速解決您的問題爲我們提供了一種快速裝箱的解決方案，所以您的問題至少同樣困難;並且由於垃圾包裝是NP-Hard，您的問題也是如此。

雖然有一些近似算法可用;例如，很容易顯示簡單的first-fit算法（將每個項目放入適合的第一個bin中）永遠不會比最佳解決方案的效果差2倍。

類似的「首次適應減少」算法（按降序進行排序的項目，然後把每一個項目在它適合進入第一倉）甚至更好，保證是內最優解的約25％。還有另一種稍微複雜的算法MFFD，它保證在20％左右。

當然，只有7個盒子，你總是可以蠻橫的解決方案。這將需要大約7 ⁿ步驟（其中n是項目的數量），所以這個解決方案是不可行的與十幾個項目。

來源

2012-04-11 21:24:06

我的問題是，我會選擇的容器大小部分取決於項目的總容量。例如：許多小件物品在大型UPS箱中發送比在許多小型USPS平板電腦箱中便宜。即隨着總體積增加，通常使用更大的箱子會更好。 – unixman83 2012-04-11 21:54:35

@ unixman83：-_-這個問題提到了將項目裝入最少的盒子，它沒有提到任何有關價值的東西。不過，我認爲你會發現你的新問題是Knapsack的泛化，所以你仍然找不到最佳解決方案：\嘗試查找一些Knapsack近似值。 – 2012-04-11 21:58:10

是的。感謝您解答我遇到的空間問題。這絕對是一個幫助。 – unixman83 2012-04-11 21:58:55

您已經描述了knapsack problem的變體。查看wikipedia article瞭解有關解決此問題的方法的更多詳細信息。

來源

2012-04-11 21:09:22

作爲一個「揹包問題的變體」並不能使它完全NP。 – 2012-04-11 21:20:01

任何指向某些代碼的指針？ – unixman83 2012-04-11 21:22:44

嘿，我沒有說這是NP完成！但是你可以寫出關於這個主題的全部書籍，我不想試圖用100字以內的數字來總結它。 – 2012-04-11 21:46:44

爲一組三維矩形物品尋找最佳3D箱子尺寸

回答

相關問題