kanpsack.py

'''
https://en.wikipedia.org/wiki/Knapsack_problem
'''

v = [1,2,3,2,10]
w = [2,5,7,8,15]
W = 22
n = len(v)
m = [[0 for _ in range(W+1)] for _ in range(n)]
for i in range(n):
	for j in range(W+1):
		if w[i] <= j:
			m[i][j] = max(m[i-1][j], m[i-1][j-w[i]]+v[i])
		else:
			m[i][j] = m[i-1][j]

for x in m:
	print x