Java中的遞歸揹包

我已經閱讀了很多揹包問題的變體，但我負責的版本有點不同，我不太明白如何解決它。Java中的遞歸揹包

我有一個代表權重的整數數組（即{1,4,6,12,7,2}），並且只需要找到一個合計目標權重的解決方案。

我明白基本的算法，但我不明白如何實現它。

首先，我的基本情況是什麼？數組是否爲空？目標已經達到？目標已經超過了？或者也許有一些組合？

其次，當目標超出時，我該如何回溯並嘗試下一個項目？

三，我應該返回什麼？我應該回國嗎（在這種情況下，我應該把它們打印出來嗎？）？或者我返回數組，最終的回報是解決方案嗎？

來源

2014-10-29 SFBA26

仔細想想你正試圖解決的問題。爲了解決這個問題，我是考慮了Knapsack算法的輸入和輸出。

輸入：一個整數集（揹包）和一個整數（所提出的總和）

輸出：一套誰加起來之和建議，或空整數。

這樣，您的代碼可能看起來像這樣

public int[] knapsackSolve(int[] sack, int prospectiveSum) { 
    //your algorithm here 
}

遞歸算法很簡單。首先計算麻袋的總和。如果它等於 prospectiveSum然後返回袋。否則，遍歷麻袋，併爲每個項目初始化一個新的揹包與該項目刪除。在這裏調用knapsackSolve。如果有解決方案，請將其退回。否則，進入下一個項目。

例如，如果我們調用knapsackSolve（{1,2,3}，5），算法會嘗試1 + 2 + 3 = 5這是錯誤的。因此它循環遍歷{1,2,3}並在子列表{2,3}，{1,3}和{1,2}上調用knapsackSolve。 knapsackSolve（{2,3}，5）是返回解決方案的一個。

這不是一個非常有效的算法，雖然它很好地說明了揹包問題有多複雜！

來源

2014-10-29 08:01:21 YardGlassOfCode

你說輸出是一組**整數，但我只在你的示例代碼中看到「int」 – 2014-10-29 12:38:25

就問題而言，輸出是一組整數。在解決方案（實現）方面，輸出是'int []'。所以我並不是指'Set '意義上的一組整數。這個解決方案使用'Set '是一個好主意，但我認爲數組會更簡單。 – YardGlassOfCode 2014-10-29 20:24:37

基本上將揹包問題表述爲（從Wikipedia）：「給定一組項目，每個項目都有一個質量和一個值，確定要包含在一個集合中的每個項目的數量，以便總重量小於或者等於一個給定的限制，並且總的值是儘可能大的，對於你的問題，我們只對權重感興趣，所以你可以將所有的值都設置爲1.此外，我們只想知道目標權重是否可以準確達到。我猜你可以只使用一次而不是多次使用重量？這個問題可以用動態編程很好地解決。你是否熟悉這個原理？應用動態編程比編程回溯更加優雅和快速。您只能使用上面發佈的user2738608的方法進行回溯。

來源

2014-10-29 12:33:54 BluesSolo

Java中的遞歸揹包

回答

相關問題