nap sack

napsack.js

 v = values from item1..itemn
    w = weights from item1..itemn
    n = number of items
    W = maximum weight of knapsack
       
    m[n, n] = array(int, int)
    function knapsack
      for w=0..W
        m[0, w] = 0
      for i=1 to n
        m[i, 0] = 0
        for w=1..W
          if w[i] <= w
            if v[i] + m[i-1, w - w[i]] > m[i-1, w]
               m[i, w] = v[i] + m[i-1, w - w[i]]
            else
               m[i, w] = m[i-1, w]
          else
            m[i, w] = c[i-1, w]
      
      return m[n, n]