01knapsack.py

def knapsack(values, weights, k, i=0, lookup=None):
    lookup = {} if lookup is None else lookup
    if (i, k) in lookup:
        return lookup[(i, k)]
    if i == len(values):
        return 0
    elif k < 0:
        return float('-inf')
    else:
        lookup[(i, k)] = max(values[i]+knapsack(values, weights, k-weights[i], i+1, lookup),
                             knapsack(values, weights, k, i+1))
        return lookup[(i, k)]

this code is not 100% correct it needs to check if weights[i] > k before adding

def find_knapsack_top(v,w, k, i=0, lookup= None):
    lookup = {} if lookup is None else lookup
    if (i,k) in lookup:
        return lookup[(i,k)]

    if len(v) == i or k < 0:
        return 0
    elif (w[i] > k):
        return find_knapsack_top(v, w, k, i+1, lookup)
    else:
        lookup[(i,k)] = max(v[i]+ find_knapsack_top(v,w,k-w[i],i+1,lookup),
                            find_knapsack_top(v, w,k,i+1, lookup))
        return lookup[(i,k)]