knapsack10.py

value = [[0 for x in xrange(0, W+1)] for x in xrange(0, n+1)]
   keep = [[0 for x in xrange(0,W+1)] for x in xrange(0, n+1)]

   for w in range(0, n): 
      value[0][w] = 0
      keep[0][w] = 0

   for i in xrange(1, n+1):
      for w in xrange(0, W+1):
         if((weight[i] <= w) and (v[i] + value[i-1][w-weight[i]] > value[i-1][w])):
            value[i][w] = v[i] + value[i-1][w-weight[i]]
            keep[i][w] = 1
         else:
            value[i][w] = value[i-1][w]
            keep[i][w] = 0
   k = W

   for i in xrange(n, -1, -1):
      if(keep[i][k]==1):
         print "value: %d - weight: %d" % (v[i], weight[i])
         k = k - weight[i]

   return value[n][W]


v = [0, 4, 3, 5]
w = [0, 1, 2, 3]
n = 3
W = 5

print knapsack(v, w, n, W)