包裝數據的不同大小的塊爲多個垃圾箱

我需要一個算法，讓我在垃圾箱塊的（節省空間）最佳安排。其中一種方法是先放大塊。但看看這個算法在這個例子中是如何失敗的：

Chunks  Bins 
----------------------------- 
AAA BBB CC DD (  ) ( ) 

Algorithm  Result 
----------------------------- 
biggest first (AAABBB) (CC) 
optimal  (AAACCDD) (BBB)

「最大的第一」不能放入DD中。也許這有助於建立一個表是這樣的：

Size 1: --- 
Size 2: CC, DD 
Size 3: AAA, BBB 

Size 4: CCDD 
Size 5: AAACC, AAADD, BBBCC, BBBDD 
Size 6: AAABBB 

Size 7: AAACCDD, BBBCCDD 
Size 8: AAABBBCC, AAABBBDD 
Size 10: AAABBBCCDD

來源

2010-12-23 dkreuter

您預計有多少個垃圾箱？它們有多大？ – 2010-12-23 18:28:41

最小的塊是12個字節。最大的塊是2 MB。所有垃圾箱的容量不得超過16 MB。 – dkreuter 2010-12-23 18:32:32

這基本上是bin-packing問題的一個變種。這個問題被稱爲NP-hard，所以不要指望爲複雜情況找到一個有效的最優算法（即有很多對象和分箱）。

但是，如果您的對象/垃圾箱數量相對較少，您可能會很好，只需使用depth-first search即可全面搜索所有可能的組合。

這很容易實現：只需取第一個對象，然後遞歸地重新運行算法，依次將第一個對象放置在每個倉中（即從可用倉空間中減去對象的大小）。最後，您只需要跟蹤迄今爲止找到的最佳「解決方案」，並在嘗試所有組合後將此作爲最終答案返回。

您可能還可以使這個算法算法的運行速度由：

考慮等同
大小相等的所有對象修剪搜索樹（即早期從一個分支返回），如果你可以」 t可能擊敗目前的最佳解決方案，例如當你已經找到了完美的契合

基於

鑑於它看起來像你有一個非常大的數字塊來處理的問題，大小的意見更新，你可能會想嘗試以下：

適合使用窮舉搜索最大的10-20塊如上
使用最大擬合方法

來源

2010-12-23 18:45:08 mikera

此問題的一個一般的最佳算法還不存在（見bin packing problem）。你可以在維基百科上找到一些不同的方法和/或谷歌搜索「垃圾箱問題」，也許「揹包問題」也可以提供一些幫助。

來源

2010-12-23 18:34:34

Donald Knuth的Dancing Links算法可快速找到「精確覆蓋」問題的解決方案。

來源

2010-12-23 18:44:41

Mikera是對的：這個多個Knapsack問題（bin裝箱問題的變體）是NP hard。

這裏有幾個你的選擇（從我的答案上類似的問題複製）：

蠻力，或者更好的是，分支定界。不會擴展（根本不！），但會找到你最佳的解決方案（儘管可能不在我們的有生之年）。
確定性算法：對最大尺寸的塊進行排序，並逐個瀏覽該列表，併爲其指定最佳剩餘點。這將完成得非常快，但解決方案可能遠不是最優的（或可行的）。 Here's a nice picture showing an example what can go wrong.但是，如果你想保持簡單，那就是要走的路。
元啓發式，從確定性算法的結果開始。這會在合理的時間內給你一個很好的結果，比人類想象的要好。取決於你給它多少時間以及問題的難度，它可能或可能不是最佳解決方案。有幾個庫在那裏，如Drools Planner（開源Java）。

來源

2010-12-24 10:14:15

包裝數據的不同大小的塊爲多個垃圾箱

回答

相關問題