bestSteal.py

def bsDo(v, s, i, j):
	global M1
	if (i == 0 and j >= s[0]):
		return v[0]
	if (i == 0 and j < s[0]):
		return 0
	if (j < s[i]):
		return bsDo(v, s, i-1, j)
	notstolen = bsDo(v, s, i-1, j)
	stolen = bsDo(v, s, i-1, j-s[i]) + v[i]
	if stolen > notstolen:
		M1[i][j] = (stolen, j-s[i])
		return stolen
	else:
		M1[i][j] = (notstolen, j)
		return notstolen

def beststealrec(v, s, C):
	global M1
	M1 = []
	for i in range(0,len(v)):
		M1.append([(-1,-1)]*(C+1))
	bsDo(v, s, len(v)-1, C)