常用算法设计思想之一：动态规划算法_动态规划算法的设计思想

#!/usr/bin/env python
# coding:utf-8
def fib(number):
    if number == 0 or number == 1:
        return 1
    else:
        return fib(number - 1) + fib(number - 2)
if __name__ == '__main__':
    print fib(35)

#!/usr/bin/env python
# coding:utf-8
cache = {}
def fib(number):
    if number in cache:
        return cache[number]
    if number == 0 or number == 1:
        return 1
    else:
        cache[number] = fib(number - 1) + fib(number - 2)
        return cache[number]
if __name__ == '__main__':
    print fib(35)

#!/usr/bin/env python
# coding:utf-8
cache = {}
items = range(0,9)
weights = [10,1,5,9,10,7,3,12,5]
values = [10,20,30,15,40,6,9,12,18]
# 最大承重能力
W = 4
def m(i,w):
    if str(i)+','+str(w) in cache:
        return cache[str(i)+','+str(w)]
    result = 0
    # 特殊情况
    if i == 0 or w == 0:
        return 0
    # w < w[i]
    if w < weights[i]:
        result = m(i-1,w)
    # w >= w[i]
    if w >= weights[i]:
        # 把第i个物品放入背包后的总价值
        take_it = m(i-1,w - weights[i]) + values[i]
        # 不把第i个物品放入背包的总价值
        ignore_it = m(i-1,w)
        # 哪个策略总价值高用哪个
        result = max(take_it,ignore_it)
        if take_it > ignore_it:
            print 'take ',i
        else:
            print 'did not take',i
    cache[str(i)+','+str(w)] = result
    return result
if __name__ == '__main__':
    # 背包把所有东西都能装进去做假设开始
    print m(len(items)-1,W)

#!/usr/bin/env python
# coding:utf-8
cache = {}
items = range(1,9)
weights = [10,1,5,9,10,7,3,12,5]
values = [10,20,30,15,40,6,9,12,18]
# 最大承重能力
W = 4
def knapsack():
    for w in range(W+1):
        cache[get_key(0,w)] = 0
    for i in items:
        cache[get_key(i,0)] = 0
        for w in range(W+1):
            if w >= weights[i]:
                if cache[get_key(i-1,w-weights[i])] + values[i] > cache[get_key(i-1,w)]:
                    cache[get_key(i,w)] = values[i] + cache[get_key(i-1,w-weights[i])]
                else:
                    cache[get_key(i,w)] = cache[get_key(i-1,w)]
            else:
                cache[get_key(i,w)] = cache[get_key(i-1,w)]
    return cache[get_key(8,W)]
def get_key(i,w):
    return str(i)+','+str(w)
if __name__ == '__main__':
    # 背包把所有东西都能装进去做假设开始
    print knapsack()

#!/usr/bin/env python
# coding:utf-8
cache = {}
# 为了下面表示方便更容易理解，数组从1开始编号
# 即当i,j为0的时候，公共子序列为0，属于极端情况
A = [0,'A','B','C','B','D','A','B','E','F']
B = [0,'B','D','C','A','B','A','F']
def C(i,j):
    if get_key(i,j) in cache:
        return cache[get_key(i,j)]
    result = 0
    if i > 0 and j > 0:
        if A[i] == B[j]:
            result = C(i-1,j-1)+1
        else:
            result = max(C(i,j-1),C(i-1,j))
    cache[get_key(i,j)] = result
    return result
def get_key(i,j):
    return str(i)+','+str(j)
if __name__ == '__main__':
    print C(len(A)-1,len(B)-1)

#!/usr/bin/python
# coding:utf-8
"""Dynamic Programming"""
CACHE = {}
# 为了下面表示方便，数组从1开始编号
# 即当i,j为0的时候，公共子序列为0，属于极端情况
A = [0, 'A', 'B', 'C', 'B', 'D', 'A', 'B', 'E', 'F']
B = [0, 'B', 'D', 'C', 'A', 'B', 'A', 'F']
def lcs_length(i, j):
    """Calculate max sequence length"""
    if get_key(i, j) in CACHE:
        return CACHE[get_key(i, j)]
    result = 0
    if i > 0 and j > 0:
        if A[i] == B[j]:
            result = lcs_length(i-1, j-1)+1
        else:
            result = max(lcs_length(i, j-1), lcs_length(i-1, j))
    CACHE[get_key(i, j)] = result
    return result
def lcs(i, j):
    """backtrack lcs"""
    if i == 0 or j == 0 :
        return ""
    if A[i] == B[j]:
        return lcs(i-1, j-1) + A[i]
    else:
        if CACHE[get_key(i-1, j)] > CACHE[get_key(i, j-1)]:
            return lcs(i-1, j)
        else:
            return lcs(i, j-1)
def get_key(i, j):
    """build cache keys"""
    return str(i) + ',' + str(j)
if __name__ == '__main__':
    print lcs_length(len(A)-1, len(B)-1)
    print lcs(len(A)-1, len(B)-1)