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

雨点打透心脏的1/2处 2022-06-09 05:42 207阅读 0赞

## 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 \]。  
递归定义最优值：  
![这里写图片描述][SouthEast]  
第一种情况：当 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。问应如何选择装入背包的物品（物品不能分割），使得装入背包中物品的总价值最大?  
![这里写图片描述][SouthEast 1]  
递归定义最优值，逆序得到最优解：  
![这里写图片描述][SouthEast 2]  
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

[SouthEast]: /images/20220609/00201400a06246e6ae3bf032a350aacd.png
[SouthEast 1]: /images/20220609/a2c291c44d844a2e9e1eaec5c0c3295c.png
[SouthEast 2]: /images/20220609/5fd2a5ce07164dee9f59de93c6387699.png