Bin包裝暴力破解方法

Question

我需要製作解決包裝包裝問題的程序，但我已經做出了第一個合適和貪婪的算法，但是我的講師說在某些情況下，它不會找到問題的最小解決方案。所以我決定嘗試暴力，但我不知道它應該如何檢查所有可能的解決方案。所以是的..有人可以向我解釋或給僞代碼或其他東西。我會很感激。

Answer 1

注意bin-packing是一個NP難問題，基本上意味着它會採取過長，以在其上運行蠻力，即使是相對較小的輸入，所以蠻力爲NP難的問題是幾乎從來沒有一個好主意 。上面的鏈接顯示了一些替代方案（或近似值）。但我會繼續...

Recursion使暴力容易。一旦你理解a basic recursive algorithm，繼續閱讀...

基本思想：（3項，2個箱，假設一切都適合，如果它不只是跳過分支）

Put the first item in the first bin. 
    Put the second item in the first bin. 
    Put the third item in the first bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the first bin and put it into the second bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the second bin. 
    Remove the second item from the first bin and put it into the second bin. 
    Put the third item in the first bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the first bin and put it into the second bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the second bin. 
    Remove the second item from the second bin. 
Remove the first item from the first bin and put it into the second bin. 
    Put the second item in the first bin. 
    Put the third item in the first bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the first bin and put it into the second bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the second bin. 
    Remove the second item from the first bin and put it into the second bin. 
    Put the third item in the first bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the first bin and put it into the second bin. 
     Woo-hoo! We have a solution! 
    Remove the third item from the second bin. 
    Remove the second item from the second bin. 
Remove the first item from the second bin. 

（見多少步驟已經有這僅僅是3個項目和2個箱）

僞代碼：

recurse(int itemID) 
    if pastLastItem(itemID) 
    if betterThanBestSolution 
     bestSolution = currentAssignment 
    return 
    for each bin i: 
    putIntoBin(itemID, i) 
    recurse(itemID+1) 
    removeFromBin(itemID, i) 

Answer 2

蠻力只是嘗試每一個組合。

要寫入蠻力的代碼，可以考慮這一招：假設我們想訪問8和王后的所有combitions，沒有硬編碼8個嵌套循環。 只需考慮由8個零組成的以下八進制數。

00000000 

然後寫一個單一的環，增加它在一個八進制數字系統：

00000001 
00000002 
00000003 
... 
00000007 // 7 + 1 = 10 
00000010 
00000011 
00000012 
... 
77777776 
77777777 

即嘗試所有組合，而無需硬碼8個的內部循環。用n替換8並且相同的代碼仍然有效。

Answer 3

可以很明顯的做的不僅僅是蠻力更好。首先你計算垃圾箱的最小數量。如果您的垃圾箱大小爲100，並且物品總大小爲1,234，則它們不適合12個垃圾箱，但可能適合13個垃圾箱。

使用13個垃圾箱，您將有66個未使用的空間（1,300 - 1,234）。由於5 x 13 = 65，所以必須至少有一個大小爲6的bin未使用。因此，如果您有任何尺寸爲6或更小的物品，您可以將其保留在計算範圍之外，因爲無論如何您最終都可以適應它（當然，您需要檢查您的實際數量，但無論如何，小物件可以從搜索中刪除）。

如果兩個項目完全填滿垃圾箱，那麼您不需要考慮任何解決方案，如果它們不在一起。

從此你使用動態編程，除了你總是在新倉使用最大的未使用的項目作爲第一個項目，你總是充滿項斌降序排列，你隨時添加更多的項目，直到沒有適合，你永遠不會考慮所有項目比其他組合的尺寸更小或尺寸相同的組合。最後，當您發現組合的數量與需要的最小數量相同時，您找到了最佳解決方案。