Sakalya Sakalya - 9 months ago 62
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.

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
      return (element1._1, element1._2 ::: element2._2)