Knapsack

We have 4 widget with values 10, 40, 30, 50 and weights 5, 4, 6, 3
We must keep our total weight to 10 and below. What combination of widgets 
will give us the largest total value that still adheres to the weight upper
bound? (Replacements are not allowed)

Well, since this is a dynamic programming problem we can use the previous result to compute the next. The final memoized grid will look like this:

v/w	0	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	10	10	10	10	10	10	10
2	0	0	0	40	40	40	40	40	40	50	50
3	0	0	0	40	40	40	40	40	40	50	70
0	0	50	50	50	90	90	90	90	90	90	90

Let's take cell (3, 10) as an example. This means that we're trying to find the maximum value if we only have the first 3 values to choose from: 10, 40, 30 and our maximum weight is 10. We have 2 choices

1. We can exclude the 3rd value i.e. 30 with a weight of 6.The previous optimum is at(2, 10) which is 50. So our (3, 10) would become 50

2. We can include the 3rd value. In order to include it, we must ensure that we do not exceed our current weight limit, 10. So we must take the optimum at (2, 10 - 6 (the weight of the 3rd value)) = (2, 4) which is 40 and add to it the value of the 3rd value: 40 + 30 = 70 This is > 50 from option 1. So our (3, 10) is 70. And we're done

We repeat this for every possible combination of (v, w)

def knapsack(vs: Vector[(Int, Int)], w: Int): Vector[Vector[Int]] =
    1.to(vs.length)
      .foldLeft(
        Vector.fill(vs.length + 1)(Vector.fill(w + 1)(0))
      )((out, currWidgetI) =>
        1.to(w).foldLeft(out) { (out, currW) =>
          val (widgetV, widgetW) = vs(currWidgetI - 1)
          if (widgetW <= currW)
            out.updated(currWidgetI, out(currWidgetI).updated(currW, Math.max(out(currWidgetI - 1)(currW), widgetV + out(currWidgetI- 1)(currW - widgetW))))
           else
            out.updated(currWidgetI, out(currWidgetI).updated(currW, out(currWidgetI - 1)(currW)))

      })