# input: v[0..N) and w[0..N) arrays of natural numbers, N>=0, and C>=0
#
# output: Maximum retribution by choosing elements with individual
#         retribution and weight in v[0..N) and w[0..N), respectively,
#         to carry in a knapsack with weight capacity C
#
# O(NC) time and O(C) space solution

def ks_tab_opt(v,w,C):
  N = len(v)
  tab = [ 0 for c in range(C+1) ]
  n,c = 1,C
  while n!=N+1:
    if c==-1: n,c = n+1,C
    else:
      if w[n-1]<=c: tab[c] = max(tab[c],v[n-1]+tab[c-w[n-1]])
      c -= 1
  return tab[C]