The Knapsack Problem, in Scala -- Keywords: dynamic programming, recursion, scala.

knapsack_problem.scala

def knapsack_aux(x: (Int, Int), is: List[Int]): List[Int] = {
  for {
    w <- is.zip(is.take(x._1) ::: is.take(is.size - x._1).map(_ + x._2))
  } yield math.max(w._1, w._2)
}

def knapsack_rec(xs: List[(Int, Int)], is: List[Int]): List[List[Int]] = {
  xs match {
    case x :: xs => knapsack_aux(x, is) :: knapsack_rec(xs, knapsack_aux(x, is))
    case _ => Nil
  }
}

/* knapsack(): return the value inside the knapsack
 * xs: list of items, pair of (weight, value)
 * k: size of the knapsack
 */
def knapsack(xs: List[(Int, Int)], k: Int): Int = {
  knapsack_rec(xs, List.fill(k)(0)).last.last
}

println(knapsack(List((1, 1), (2, 2)), 4))
println(knapsack(List((1, 1), (2, 2)), 5))
println(knapsack(List((1, 1), (2, 2), (2, 4)), 5))