#This is the 0-1 Knapsack problem, This is implemented in two ways.
#The trivial way is using recursion (maxVal) and the dynamic programming
#(maxVal0) the latter is using memoization.
#without memoization
def maxVal(w, v, i, aW):
    print('maxVal called with:' + str(i) + str(aW))
    global NumCalls
    NumCalls += 1
    if i == 0:
        if w[i] <=aW: return v[i]
        else: return 0
    without_i = maxVal(w, v, i-1, aW)
    if w[i] > aW:
        return without_i
    else:
        with_i = v[i] +maxVal(w, v, i-1, aW-w[i])
    return max(with_i, without_i)

#With memoization
def fastMaxVal(w, v, i, aW, m):
    print('maxVal called with:' + str(i) + str(aW))
    global NumCalls
    NumCalls += 1
    try: return m[(i, aW)]
    except KeyError:
        if i == 0:
            if w[i] <=aW: 
                m[(i, aW)] = v[i]
                return v[i]
            else: 
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal(w, v, i-1, aW, m)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return without_i
        else:
            with_i = v[i] +fastMaxVal(w, v, i-1, aW-w[i], m)
        res = max(with_i, without_i)
        m[(i, aW)] = res
        return res
#Function that calls fastMaxVal
def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal(w, v, i, aW, m)


#weights = [1, 1, 5, 5, 3, 3, 4, 4]
#vals = [15, 15, 10, 10, 9, 9, 5, 5]
#totwt = 8
weights = [1,  1,  5,  5,  3, 3]
vals    = [15, 15, 10, 10, 9, 9]
totwt = 8
#weights = [1, 5, 3, 4]
#vals = [15, 10, 9, 5]
#totwt = 8
#weights = [5, 3, 2]
#vals = [9, 7, 8]
#totwt = 5
NumCalls = 0
res = maxVal(weights, vals, len(vals)-1, totwt)
print ('maxVals = ' + str(res) + ', number of Calls = ' + str(NumCalls) )
NumCalls = 0
res = maxVal0(weights, vals, len(vals)-1, totwt)
print ('fastMaxVals = ' + str(res) + ', number of Calls = ' + str(NumCalls) )
