from collections import defaultdict
CS = defaultdict(lambda: defaultdict(int))
def zeroOneKnapSack(numItems, sackSize, weights, values):
     
    if CS[numItems][sackSize] != 0:
        return CS[numItems][sackSize]
    if (numItems == 0) or (sackSize==0):
        CS[numItems][sackSize] = 0
        return 0
    if weights[numItems] > sackSize:
        CS[numItems][sackSize] = zeroOneKnapSack(numItems-1, sackSize, weights, values)
        return CS[numItems][sackSize]
 
    CS[numItems][sackSize] = max( values[numItems]+zeroOneKnapSack(numItems-1, sackSize-weights[numItems], weights, values), 
                                  zeroOneKnapSack(numItems-1, sackSize, weights, values) )
     
    return CS[numItems][sackSize]


weights = [5,4,6,3]
values = [10,40,30,50]
sackSize = 10
#another testcase
# weights = [1,3,4,5]
# values = [1,4,5,7]
# sackSize = 7
numItems = len(weights)-1 #could also use len(values)-1
print zeroOneKnapSack(numItems, sackSize, weights, values)