Dynamic programming in Python, MIT Intro to CS Programming, LECTURE 12 & 13

dp.py

# def fib(n):
#     global numCalls
#     numCalls += 1
#     print 'fib called with', n
#     if n == 0 or n == 1:
#         return 1
#     else:
#         return fib(n-1) + fib(n-2)

# # numCalls = 0
# # n = 6
# # res = fib(n)
# # print 'fib1 of', n, ' = ', res, 'numCalls = ', numCalls

# def fastFib(n, memo):
#     global numCalls
#     numCalls += 1
#     print 'fib1 called with', n
#     if n not in memo:
#         memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
#     return memo[n]
# def fib1(n):
#     memo = {0: 1, 1:1}
#     return fastFib(n, memo)
        
        
# numCalls = 0
# n = 6
# res = fib1(n)
# print 'fib1 of', n, ' = ', res , 'numCalls = ', numCalls

def maxVal(w, v, i, 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)

def fastMaxVal(w, v, i, aW, m):

    try:
        return m[(i, aW)]

    except KeyError:
        global numCalls
        numCalls += 1
        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:
            res[(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
def fastMaxVal0(w, v, i, aW, m):
    if (i, aW) not in m:
        if i == 0:
            if w[i] <= aW:
                m[(i, aW)] = v[i]
                return v[i]
            else:
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal0(w, v, i-1, aW, m)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return m[(i, aW)]
        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
            
        
def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal0(w, v, i, aW, m)
weights = [5, 3, 2]
values = [9, 7, 8]
numCalls = 0
print maxVal(weights, values, len(weights) - 1, 5)
print 'numCalls = ', numCalls

weights = [5, 3, 2]
values = [9, 7, 8]
numCalls = 0
print maxVal0(weights, values, len(weights) - 1, 5)
print 'numCalls = ', numCalls