Knapsack problem #2

gistfile1.py

def solve(k, a):
	b = []
	for i in range(len(a)):
		b.append([None]*(k+1))
		
	b[0][0] = 1
	b[0][a[0]] = 1

	for i in range(1, len(a)):
		for j in range(k+1):
			if b[i-1][j]:
				b[i][j] = 1 # not include current
				if j + a[i] <= k:
					b[i][j + a[i]] = 1 #include current
					
	return bool(b[-1][-1])

a = [2, 43, 6546457, 4, 5, 7, 34, 1]
k = 15
print solve(k, a)