数据结构与算法之动态规划算法及其python实现-蒲公英云

数据结构与算法之动态规划算法及其python实现

1 动态规划问题

动态规划算法和分治法类似，都是将带求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的答案。与分治法不同的是，动态规划要用一个表来记录所有已解决的子问题的答案。不管该问题是否以后会被用到，只要它被计算过，就将其结果填入表中。在需要时从表中找出答案，避免大量重复计算，从而得到多项式时间算法。通常按一下几个步骤设计动态规划算法：
（1）找出最优解性质，刻画最优解结构；
（2）递归的定义最优值；
（3）以自底向上的方式计算最优值；
（4）根据计算最优值得到的信息，构造最优解。
具体实例有：矩阵连乘，最长公共子序列，流水调度作业，0-1背包问题，最优二叉搜索树等。

2 最长公共子序列

2.1 原理

问题描述：给定两个序列 X = { x1, x2, …, xm }和Y = { y1, y2, …, yn }，找出X和Y的最长公共子序列。
最优解：最长公共子序列的长度 m[ i ][ j ]以及相应的位置b[ i ][ j ]。
递归定义最优值：
这里写图片描述
第一种情况：当 i = 0，或者 j = 0 时，长度为 0；
第二种情况：当 xi = yi 时，表示长度等于子序列（去掉 i 位置元素后的序列）+1， 1 表示xi(或者 yi )；b[ i ][ j ] = 1
第三种情况：当 xi ！= yi 时，表示两个不同子序列公共长度的最大值。 b[ i ][ j ]=2,b[ i ][ j ]=3

2.2 时间复杂度和空间复杂度

时间复杂度： 需要计算每个 c[ i ][ j ]的大小，所以时间为 mn；
空间复杂度： 需要存储c[ i ][ j ]，所以空间为 mn。

2.3 python代码

#coding:utf-8
def LCS(i,j,X,b,out):   #得到最长子序列
    if i == -1 or j == -1:
        return
    if b[i][j] == 1:
        print i,j
        out.append(X[i])
        LCS(i-1,j-1,X,b,out)
    elif b[i][j] == 2:
        LCS(i-1,j,X,b,out)
    elif b[i][j] == 3:
        LCS(i,j-1,X,b,out)
    print out
    return out
def lcsLength(X,Y):  #计算最长子序列的长度，以及位置i,j 
    m = len(X)
    n = len(Y)
    c = {}
    c[-1] = {}
    b = {}
    for i in range(m):
        c[i] = {}
        c[i][-1] = 0
    for j in range(n):
        c[-1][j] = 0
    for k in range(m):
        b[k] = {}
    for i in range(m):        #外循环
        for j in range(n):    #内循环
            if X[i] == Y[j]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = 1
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = 2
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = 3
            print i,j,c[i][j]
    print c[m-1][n-1]
    out = []
    out = LCS(m-1,n-1,X,b,out)
    print out[::-1]
X = raw_input().split()
Y = raw_input().split()
lcsLength(X, Y)

3 0-1背包问题

3.1 原理

问题描述：给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?
这里写图片描述
递归定义最优值，逆序得到最优解：

m( i , j )表示最优值总价值，Wi 表示第 i 件物品的重量， Vi 表示第 i 见物品的价值，i 表示剩下的还可以选择是否装入的物品有 i,i+1,i+2,….,n ; j 表示剩余的空间；
从上往下依次情况是：
（1）装到第 i 见物品时，当剩余空间大于等于这件物品的重量，意思是可以装下这件物品，那么可以选择装还是不装，取决于两种情况的价值；
（2）装到第 i 见物品时，当剩余空间小于这件物品的重量，装不下这件物品;
（3）第n 件物品，如果能装下，就装入；
（4）第n 件物品，如果不能装下，就不装了；

3.2 时间复杂度和空间复杂度

时间复杂度： 需要计算每个 m[ i ][ j ]的大小，所以时间为 num*C；
空间复杂度： 需要存储m[ i ][ j ]，所以空间为 num*C。

3.3 python 代码

#coding:utf-8
def traceback(num,m,w,C):
    x = {}
    for i in range(num-1):
        if m[i][C] == m[i+1][C]:
            x[i] = 0               #没装
        else:
            x[i] = 1
            C -= w[i]
        if m[num-1][C] > 0:
            x[num-1] = 1
        else:
            x[num-1] = 0
    print x
    value = 0
    for j in x:
        if x[j] == 1:
            value += v[j]
        else:
            continue
    print "总价值",value
def backpack(num,v,w,C):
    print num,v,w,C
    jMax = min(w[num-1]-1,C)
    m = {}
    m[num-1] = {}
    for j in range(jMax+1):
        m[num-1][j] = 0
    for j in range(w[num-1],C+1):
        m[num-1][j] = v[num-1]
    i = num-2
    for k in range(num-1):
        m[k] = {}
    while i > 0:
        jMax = min(w[i]-1,C)
        for j in range(jMax+1):
            m[i][j] = m[i+1][j]
        for j in range(w[i],C+1):
            m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i])
        i -= 1
    m[0][C] = m[1][C]
    if (C > w[0]):
        m[0][C] = max(m[1][C],m[1][C-w[0]+v[0]])
    traceback(num,m,w,C)
num = raw_input(u"请输出带装入的物品个数:")
num = int(num)
v = raw_input("请输入每个物品的价值：")
v = [int(i) for i in v.split()]
w = raw_input("请输入每个物品的重量:")
w = [int(i) for i in w.split()]
C = raw_input("请输入背包的容量：")
C = int(C)
backpack(num,v,w,C)
请输出带装入的物品个数:5
请输入每个物品的价值：1 2 3 4 5
请输入每个物品的重量:1 2 3 4 5
请输入背包的容量：10
5 [1, 2, 3, 4, 5] [1, 2, 3, 4, 5] 10
{ 0: 0, 1: 1, 2: 1, 3: 0, 4: 1}
总价值 10