title: Adding memoization to recursive knapsack solution
body: <p>I'm playing with Knapsack (for no real good reason, just trying to remove some rust) and wanted to implement it in my favorite language </p>
  
  <p>(please don't laugh, it's been a while since college, and I'm pretty new to Scala) </p>
  
  <p>Here is my first run (it returns the right solution, but I think it's far from optimal):</p>
  
  <pre><code>import scala.collection.mutable.HashMap
  
  object Main {
    def main(args: Array[String]) {
      val weights = List(23, 31, 29, 44, 53, 38, 63, 85, 89, 82)
      val values = List(92, 57, 49, 68, 60, 43, 67, 84, 87, 72)
      val wv = weights zip values
      val solver = new KnapSackSolver()
      solver.solve(wv, 165) 
  
    }
  
    class KnapSackSolver() {
  
      var numberOfIterations = 0
      type Item = (Int, Int)
      type Items = List[Item]
  
      val cache = new HashMap[(Items, Int), Items]()
  
      def sackValue(s: Items) = if (s.isEmpty) 0 else s.map(_._2).sum
  
      def solve(wv: Items, capacity: Int) = {
        numberOfIterations = 0
        val solution = knapsack(wv, capacity)
  
        println(s"""|Solution: $solution
                    |Value: ${sackValue(solution)}
                    |Number of iterations: $numberOfIterations
        """.stripMargin)
  
        solution 
      }
  
      private[this] def knapsack(wv: Items, capacity: Int): Items = {
        numberOfIterations +=1
        val cacheKey = (wv, capacity)
        if (cache.contains(cacheKey)) {
          return cache(cacheKey) //I know, I wrote a return, just wanted an early exit
        }
  
        if (capacity &lt;= 0 || wv.isEmpty) {
          Nil
        } else if (wv.head._1 &gt; capacity) {
          knapsack(wv.tail, capacity)
        } else {
          val sackNotTakingCurrent = knapsack(wv.tail, capacity)
          val sackTakingCurrent = knapsack(wv.tail, capacity - wv.head._1) :+ wv.head
  
          val notTakingCurrentValue = sackValue(sackNotTakingCurrent)
          val takingCurrentValue = sackValue(sackTakingCurrent)
          val ret =
            if (notTakingCurrentValue &gt;= takingCurrentValue) sackNotTakingCurrent
            else sackTakingCurrent
  
          cache(cacheKey) = ret
          ret
        }
      }
    }
  }
  </code></pre>
  
  <p><strong>Question</strong></p>
  
  <p>My naive "caching" seems not good enough (565 vs 534 iterations) but I'm not sure how to improve it, I have a feeling that filling a matrix of size itemsXweight is involved, but not sure where to go from here. </p>
  
  <p>In other words - Is this the optimal solution? Feels very exponential to me, but then I will lie if I say I understand what pseudo polynomial really means... 
  If this not the optimal solution, which I suspect it's not, what am I missing to get there? </p>