import random
C=400
w=[]
v=[]
for i in range(38):
  w=w+[random.randrange(1,50)]
for j in range(38):
  v=v+[random.randrange(1,50)]
val = [[0 for i in range(C+1)] for j in range(len(w))]
#print val
items = [[0 for i in range(C+1)] for j in range(len(w))]
#print items
for i in range(len(w))[1:]:
  for j in range(C+1)[1:]:
    if ((w[i]<=j) and (val[i-1][j] < v[i] + val[i-1][j-w[i]])):
      items[i][j] = i
      val[i][j] = v[i] + val[i-1][j-w[i]]
    else:
      items[i][j] = items[i-1][j]
      val[i][j] = val[i-1][j]
print (val)
#print (items)
print (" total value obtainable is ", val[len(w)-1][C], " euro.")
i = len(w)-1
j = C
weight = C
while (items[i][j]!=0):
  if (items[i][j]==i):
    print (" choose item number " , i, ": remaining capacity is" , weight - w[items[i][j]], " kg.")
    weight = weight - w[i]
    j = j-w[i]
    i = i-1
  else:
    i=i-1