2014-10-29 86 views
0

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

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

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

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

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

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

回答

0

仔細想想你正試圖解決的問題。爲了解決這個問題,我是 考慮了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)是返回解決方案的一個。

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

+0

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

+0

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

0

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