Dynamic Programming Example

Dynamic Programming Example¶

(Lesson 4: Maximumim Weighted Independent Set on a Line)¶

http://www.ioinformatics.org/oi/pdf/v9_2015_45_55.pdf

In [1]:

v = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1]

In [2]:

def solve(k):
    if k == 1: return v[0]
    if k == 2: return max( v[0],v[1] )
    return max( solve(k-1), v[k-1] + solve(k-2) )

In [3]:

import time
t=time.time()
print(solve(8))
print("elapsed time: ",time.time()-t)

22
elapsed time:  0.0

The recursive dynamic programming solution solves the problem quickly for N=8.

However, for N=36 the recursive solution is much slower.

In [4]:

t=time.time()
print(solve(36))
print("elapsed time: ",time.time()-t)

100
elapsed time:  17.815231323242188

Adding Memoization to the Solve function increases the speed considerably

In [5]:

__solve_cache = {}

def solve2(k):
    if k in __solve_cache:
        return __solve_cache[k]
    elif k == 1:
        __solve_cache[k] = v[0]
    elif k == 2:
        __solve_cache[k] = max( v[0], v[1] )
    else:
        __solve_cache[k] = max( solve2(k-1), v[k-1] + solve2(k-2) )
        
    return __solve_cache[k]

In [6]:

t=time.time()
print(solve2(36))
print("elapsed time: ",time.time()-t)

100
elapsed time:  0.0

Even N=50 can be solved instantly with the Memoized version

In [7]:

t=time.time()
print(solve2(50))
print("elapsed time: ",time.time()-t)

138
elapsed time:  0.0