Knapsack Solution using Recursion

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 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 ?

score 2 · Answer 1 · edited May 23 '17 at 10:30

In your code, you already know if you chose the current element or not.

If you picked element1 (it is higher than element2), then the last (index=n-1) element was picked. Otherewise, you didn't.

So, you can add another output argument to be returned from the recursive call, that will indicate the chosen elements.

And you will need to modify all return ... to also take care of it:

return 0 will become return (0,[])
return knapsack(availableMoney,wt,value, n - 1) stays as is.
return max(element1,element2) will return (element1, list1.add(n-1)) or (element2, list2), depending on which is higher, element or element2.

Also, if you want to implement is as Dynamic programming, this question discusses how to return the elements and not only values:

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

score 1 · Accepted Answer · edited May 23 '17 at 12:26

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

Knapsack Solution using Recursion

2 Answers2