Sakalya - 3 months ago 37

Scala Question

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`

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

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