Sakalya - 1 year ago 94
Scala Question

# Knapsack Solution using Recursion

I am trying to solve Knapsack problem using recursion in Scala but my requirement is to show which items are chosen to keep in Knapsack.

`availableMoney`
indicates the knapsack size.

My code is as follows:

``````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);
}
}
``````

How to know which items are picked to keep in Knapsack ?

Answer Source

Please consider accepting amit's solution as the answer, I just want to supplement additional note on top of his solution here.

In this solution, I will also cater the case when the knapsack solution is not unique.

As pointed out by amit, it is straight-forward to modify your code to keep track of the elements in the knapsack. Your method should return a `tuple` instead of the knapsack value, where the first entry is the "max value" of the knapsack, and the second entry is a list of list of elements in the knapsack that represents of the combinations of items in the knapsack.

• The first `if` corresponds to the termination condition of the recursion, and there is only one possible combination in the knapsack - knapsack without any element.
• If the condition of the second `if` is true, then item `n - 1` cannot be picked so we recur to the next item.
• On the other hand, if the weight of item `n - 1` is less than `availableMoney`, then we can either pick item `n - 1` in the construction (this corresponds to `element1`), or leave item `n - 1` out in the construction. The returned solution should then be the better one of the two, or merging them together if they give the same value.

Below is a modified version of code for your reference:

``````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)
}
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download