【数据结构】动态规划

一.算法总体思想

1.总体思想：

将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是独立的，使用分治法求解时，有些子问题被重复计算了许多次。

2.如何改进子问题被重复计算？

如果能够保存已解决的子问题的答案，在需要时再找出已求得的答案，就可以避免大量重复计算。

3.动态规划的基本步骤：

1）找出最优解性质，并刻画起结构特征。（寻找最优解的子问题结构）

2）递归的定义最优值（根据子问题结构建立问题的递归解式）

3）自底向上的方式计算出最优值（动态规划思想）

4）根据计算最优值时得到的信息，构造最优解。

二.动态规划例子

1.权重化的活动安排问题

问题描述：

有n个活动，活动j在 $s_j$ 时刻开始， $f_j$ 时刻结束，活动j具有价值 $v_j$ ,如果两个活动不重叠，则这两个活动是可以兼容的，目标是，在确定的时间段内，找到具有最大价值且相互兼容的活动子集。

1.1 问题分析：

将活动按照结束时间从小到大进行排序 $f_1\leq f_2\leq ...\leqslant f_n$

定义p(j)=最接近活动j并且与活动j兼容的活动序号i，i<j

定义OPT（j）=j个活动（1，2，…,j）所获得的最大价值，即：最优解

1.2 最优子结构与子问题分析：

情况1：OPT（j）中包含第j个活动

必定包含由1，2，…,p(j)个活动构成的最优解

情况2:OPT（j）没有选择第j个活动

必定包含活动1，2，…,j-1个活动所构成的最优解

$OPT(j)= \begin{cases} 0 & if \quad j=0 \\ max\{v_j+OPT(p(j)),OPT(j-1)\} & otherwise \\ \end{cases}$

2.多个矩阵连乘模块设计

2.1 引理：

对于一个q*p矩阵A和一个p*r矩阵B，AB需要多少次标准乘法计算？

答案是：q*p*r

2.2 问题描述：

给定n个矩阵 $\{A_1A_2...A_n\}$ ，其中 $A_i$ 与 $A_{i+1}$ 是可乘的（i=1，2，…,n-1），考察这n个矩阵的连乘积 $A_1A_2...A_n$

由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号。

2.3 问题分析：

将矩阵连乘积 $A_iA_{i+1}...A_j$ 简记为A[i:j]，这里 $i\leqslant j$ ;

考察计算A[i:j]的最优计算次序。

设这个计算次序在矩阵 $A_k$ 和 $A_{k+1}$ 之间将矩阵链断开， $i\leqslant k<j$ 。

则其相应完全加括号的方式为 $(A_iA_{i+1}...A_k)(A_{k+1}A_{k+2}...A_j)$

总计算量=A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。

特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。

矩阵连乘计算次序问题的最优解包含着其子问题的最优解，所以具有最优子结构性质。

2.4 建立递推关系式：

设计算A[i:j], $1\leqslant i\leqslant j\leqslant n$ ,所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]

当i=j时，m[i,j]=0;

当i<j时， $m[i,j]=min\{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\}$

可以递归的定义m[i,j]为：

$m[i,j]= \begin{cases} 0 & i=j \\ min_{i\leqslant k<j} \{m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\} & i<j \\ \end{cases}$

k的位置只有j-1种可能

使用动态规划解决此问题，可以根据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案，每个子问题只计算一次，而在后面需要的时候简单的查一下，从而避免了大量的计算。

对于m[i][j]数组，只需要填入上三角中的元素即可（因为i<=j）。

每次按照对角线的方式去填写m[i][j]数组中的元素，首先将主对角线中的元素全部置为0，相当于初始化的作用。

2.5 算法时间复杂度：

$O(n^3)$

3. 0-1背包问题

3.1 问题描述：

给定n中物品和一个背包，物品i的重量 $w_i$ >0,其价值 $v_i>0$ ,背包容量为C。

应如何选择装入背包的物品，使得装入背包中物品的总价值最大且总重量不超过C？

装入方法：

每种物品只有两种选择，即装入背包或不装入。不能将物品多次装入或部分装入。

问题可以进一步抽象为：找出n元向量 $y_1,y_2,...,y_n$ ，满足约束条件下的最优化问题。

求： $max\sum_{i=1}^{n}v_ix_i$

约束条件为： $\begin{cases} \sum_{i=1}^{n}w_ix_i\leqslant C \\ x_i \in \{0,1\} & 0 1\leqslant i\leqslant n \\ \end{cases}$

3.2 分析子问题结构：

假设 $(y_1,y_2,...y_n)$ 是一个最优解，则 $(y_2,...,y_n)$ 是下面相应子问题的一个最优解

$max \sum_{i=2}^{n}v_ix_i$

$\begin{cases} \sum_{i=2}^{n}{w_ix_i}\leqslant C-w_1y_1 \\ x_i \in \{0,1\} & 2\leqslant i\leqslant n\\ \end{cases}$

分析过程1:

定义OPT(n)=由1,…,n个物体装填背包所产生的最大价值

case 1:OPT不选择第n个物体

OPT为{1,2,…,n-1}个物体装填背包所产生的最大价值

case 2:OPT选择第n个物体进行装填

接收物体n并不意味着我们必须拒绝其他物体

在不知道其他哪些物体已经在n前被选择的情况下，我们也并不能知道是否有足够的空间能容纳物体n

证明：

用反证法证明

若不然，设 $(z_2,...z_n)$ 是子问题的一个最优解，而 $(y_2,...,y_n)$ 不是最优解，由此可知：

$\sum_{i=2}^n{v_iz_i}>\sum_{i=2}^n{v_ix_i}$

且 $w_1y_1+\sum_{i=2}^n{v_iz_i}\leqslant C$

因此 $v_1y_1+\sum_{i=2}^n{v_iz_i}>\sum_{i=2}^n{v_iy_i}$

这说明 $(y_1,z_2,...,z_n)$ 是所给0-1背包问题的更优解，从而 $(y_1,y_2,...y_n)$ 不是问题的最优解。

分析过程2:

添加一个变量j

定义m(i,j)=背包容量为j，由1,…,i个物体装填背包问题的最优值。

case 1:m(i,j)不选择第i个物体

m(i,j)为{1,…,i-1}个物体装填背包所产生的最大价值，当重量限制为j

case 2:m(i,j)选择第i个物体

新的重量限制= $j-w_i$

m(i,j)为新重量限制下，{1,…i-1}个物体装填背包所产生的最大价值

递推关系式如下：

$m(i,j)= \begin{cases} 0 & if \quad i=0 \\ m(i-1,j) & if \quad w_i>j \\ max\{m(i-1,j),m(i-1,j-w_i)+v_i\} &otherwise \\ \end{cases}$

3.3 代码实现：

void knapsack(int v[],int w[],int c,int n){//v表示价值，w表示重量，c表示背包容量,n表示物品种类
    int m[MAX_SIZE][MAX_SIZE]={0};//m[i,j]=背包容量为j，由1,...,i个物体装填背包问题的最优值
    int i,j;
    for(j=0;j<=c;j++){//0个物体时
        m[0][j]=0;
    }
    for(i=0;i<n;i++){//从物品0到物品n-1
        for(j=1;j<=c;j++){//重量从1到c
            if(w[i]>j){
                m[i][j]=m[i-1][j];
            }
            else{
                m[i][j]=max(m[i-1][j],v[i]+m[i-1][j]);
            }
            
        }
    }
}

时间复杂度： $O(n*c)$

4.最长公共子序列问题：

4.1 问题描述：

给定两个字符序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。找到两个序列的最长公共子序列。

若给定序列 $X=\{x_1,x_2,...,x_m\}$ ，则另一序列 $Z=\{z_1,z_2,...z_k\}$ ，是X的子序列是指:存在一个严格递增下标序列 $\{i_1,i_2,...,i_k\}$ 使得对于所有 $j=1,2,...,k$ ，有： $z_j=x_{ij}$

例如，序列 $Z=\{B,C,D,B\}$ 是序列 $X=\{A,B,C,B,D,A,B\}$ 的子序列，相应的递增下标序列为{2,3,5,7}

4.2 问题分析：

设序列 $X=\{x_1,x_2,...,x_m\}$ ， $Y=\{y_1,y_2,...,y_n\}$ 的最长公共子序列为 $Z=\{z_1,z_2,...z_k\}$

1）若 $x_m=y_n$ ,则 $z_k=x_m=y_n$ ，且 $z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的最长公共子序列。

2）若 $x_m \neq y_n\quad z_k \neq x_m$ ,则Z是 $X_{m-1}$ 和Y的最长公共子序列。

3）若 $x_m \neq y_n \quad z_k\neq y_n$ ,则Z是 $Y_{n-1}$ 和X的最长公共子序列。

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。

设c[i][j]表示序列X和序列Y的最长公共子序列的长度。

建立递推式如下：

$c[i][j]= \begin{cases} 0 &i=0,j=0 \\ c[i-1][j-1]+1 &i,j>0;x_i=y_j \\ max\{c[i][j-1],c[i-1][j]\} &i,j>0;x_i \neq y_j \end{cases}$

int LCS(char x[],char y[],int len1,int len2,int a[],int b[]){
    int i,j,k;
    int c[MAX_SIZE][MAX_SIZE]={0};
    for(i=0;i<len1;i++){//初始化部分
        c[i][0]=0;
    }
    for(i=0;i<len2;i++){//初始化部分
        c[0][i]=0;
    }
    for(i=1;i<len1;i++){
        for(j=1;j<len2;j++){
            if(x[i]==y[j]){
                c[i][j]=c[i-1][j-1]+1;
                a[i]=1;
                b[i]=1;
            }
            else if(c[i-1][j]>=c[i][j-1]){
                c[i][j]=c[i-1][j];
            }
            else{
                c[i][j]=c[i][j-1];
            }
        }
    }
    return c[len1-1][len2-1];
}

原文链接：https://blog.csdn.net/Hsianus/article/details/135173295