使用遞歸的揹包解決方案

Question

我想在Scala中使用遞歸來解決揹包問題，但我的要求是顯示選擇哪些項目保留在揹包中。 availableMoney表示揹包大小。

我的代碼如下：

def knapsack(availableMoney: Int,wt:List[Int],value :List[Int] ,n:Int) : Int= { 

    if(n == 0 || availableMoney == 0) 
    return 0 
    if (wt(n - 1) > availableMoney) {  
    return knapsack(availableMoney,wt,value, n - 1) 
    } 
    else { 
    var element1 = value(n-1) + knapsack(availableMoney- wt(n-1), wt, value, n-1) 
    var element2 = knapsack(availableMoney, wt, value, n-1) 

    return max(element1,element2); 
    } 
} 

如何知道哪些項目被選中，保持揹包？

Answer 1

請考慮接受amit的溶液，作爲回答，我只是想在這裏補充一下他的解決方案。

在這個解決方案，我也將滿足的情況下，當揹包的解決方案是不是唯一。

正如amit所指出的那樣，修改代碼以便跟蹤揹包中的元素是直接的。你的方法應該返回一個tuple而不是揹包值，其中第一個入口是揹包的「最大值」，第二個入口是揹包中表示揹包中物品組合的元素列表。

• 第一if對應於遞歸的終止條件，並且僅存在一個在揹包可能的組合 - 揹包沒有任何元件。
• 如果第二個if的條件爲真，則不能挑選物品n - 1，因此我們重複下一個項目。
• 在另一方面，如果項目n - 1的重量小於availableMoney，那麼我們就可以挑選項目n - 1建築（相當於element1），或離開項目n - 1出在施工。所返回的解決方案應該是兩者中較好的一個，或者如果它們具有相同的價值，則將它們合併在一起。

下面的代碼，供大家參考修改後的版本：

def knapsack(availableMoney: Int, wt: List[Int], value: List[Int], n: Int): (Int, List[List[Int]]) = { 

    if (n == 0 || availableMoney == 0) 
    return (0, List[List[Int]](List[Int]())) 

    if (wt(n - 1) > availableMoney) { 
    return knapsack(availableMoney, wt, value, n - 1) 
    } else { 
    val recur = knapsack(availableMoney - wt(n - 1), wt, value, n - 1) 
    val element1 = (recur._1 + value(n - 1), for (e <- recur._2) yield {e :+ wt(n - 1)}) 
    val element2 = knapsack(availableMoney, wt, value, n - 1) 

    if (element1._1 > element2._1) 
     return element1 
    else if (element1._1 < element2._1) 
     return element2 
    else 
     return (element1._1, element1._2 ::: element2._2) 
    } 
} 

Answer 2

在你的代碼中，你已經知道你是否選擇了當前元素。

如果您選擇element1（它高於element2），則選擇最後一個（index = n-1）元素。另外，你沒有。

因此，您可以添加另一個輸出參數，以便從遞歸調用中返回，這將指示所選元素。

你會需要修改所有return ...也照顧它：

• return 0將成爲return (0,[])
• return knapsack(availableMoney,wt,value, n - 1)住宿原樣。
• return max(element1,element2)將返回(element1, list1.add(n-1))或(element2, list2)，這取決於哪個更高，element或element2。

另外，如果你想實現是動態規劃，這個問題討論瞭如何返回的元素，而不僅僅是值：

How to find which elements are in the bag, using Knapsack Algorithm [and not only the bag's value]?