I've got the imperative styled solution working perfectly.What I'm wondering is how to make a recursive branch and bound.This is my code below, Evaluate function returns the optimistic estimate, the largest possible value for the set of items which fit into the knapsack(linear relaxation).For some inputs this outputs an optimal solution, for some it comes really close, for every input it is extremely fast, so it doesn't seem that it hangs anywhere in the search space. So, maybe I'm not branching where I have to or I did something wrong. I'm sure optVal is optimal.def branch(items: List[Item], taken: List[Item], capacity: Int, eval: Long): (List[Item], Boolean) = items match {  case x :: xs if x.weight <= capacity => {    val (bestLeft, opt) = branch(xs, x :: taken, capacity - x.weight, eval)    if (opt) (bestLeft, opt) // if solution is optimal get out of the tree    else {      val evalWithout = evaluate(taken.reverse_:::(xs))      if (evalWithout < optVal) (bestLeft, opt)      else branch(xs, taken, capacity, evalWithout)    }  }  case x :: xs => branch(xs, taken, capacity, evaluate(taken.reverse_:::(xs)))  case Nil => if ((taken map (_.value) sum) == optVal) (taken, true) else (taken, false)}
Recursive branch and bound for knapsack problem
scala;recursion