遞歸裝箱算法不能擴展

Question

我完成作業，其規格要求：

• 遞歸解決方案
• 容量< = 100
• values.length < = 25
• 參數只有能力和索引
• 允許重複值

我已經花了數小時閱讀垃圾箱包裝和揹包問題。

以下工作但效率非常低。我得到了一堆有十幾個值的堆棧溢出。非常低效，不擴展，我不知道從哪裏開始。

建議將不勝感激。是的，這是一個學術任務，但我寧願排出來的問題，而不是乾脆放棄，賺取B.

public void calculateCombinations(int capacity, int index) { 
    count++; 
    if(index < values.length) { 
     if(values[index] <= capacity) { 
      currentSolution.addLast(index); 
      if(values[index] == capacity) 
       flushSolution(); 
      else 
       capacity -= values[index]; 
     } 
     calculateCombinations(capacity, index + 1); 
    } else 
     if(currentSolution.peekLast() != null) 
      calculateCombinations(capacity + values[currentSolution.peekLast()], currentSolution.removeLast() + 1); 
} 

Answer 1

關鍵啓發式裝箱問題是包裝都最尷尬（最大）項目第一。例如，如果你正在包裝一輛移動的卡車，你先把鋼琴放好，然後再擔心小的東西。這個想法是最大限度地提高靈活性。

另一種技術就是我所說的「包圍」。假設你正在尋找總計爲50的兩個數字，並且你有一個像{2,3,9,18,24,29,37,45}這樣的列表。您不必檢查每個組合，因爲您不能有超過25或25以下的兩個值。您只需檢查列表兩邊的數字，即45 + 2,45 + 3，45 + 9，STOP，下一個數字，37 + 2，37 + 3等。這是括號。通過圍繞平均值創建一組規則和包圍，您只需檢查一小部分可能的組合。

裝箱問題是一個搜索問題，因爲在許多情況下，因爲您無法列舉每種可能的組合。這就像國際象棋;你無法計算出每一個可能的舉動，你只是想找到一個好的舉動。