【算法设计与分析】第四章动态规划

痛定思痛。 2023-07-18 09:23 64阅读 0赞

## 动态规划的基本思想 ##

*  动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
 *  基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
 *  适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
 *  如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

## 设计动态规划法的步骤 ##

1.  找出最优解的性质，并刻画其结构特征；
2.  递归地定义最优值（写出动态规划方程）；
3.  以自底向上的方式计算出最优值；
4.  根据计算最优值时得到的信息，构造一个最优解。

ps：步骤1～3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略；若需要求出问题的一个最优解，则必须执行步骤4。

## 动态规划问题的特征 ##

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：  
**最优子结构：**  
当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。  
**重叠子问题**：  
在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

## 一些典型例题 ##

**一、矩阵连乘积问题**  
**【问题】**  
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少？  
**【分析】**  
将矩阵连乘积AiAi+1…Aj 简记为A\[i:j\], 这里i≤j;考察计算A\[1:n\]的最优计算次序。  
设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤k<n，则其相应完全加括号方式为(A1A2…Ak)(Ak+1Ak+2…An)。  
计算A\[1:n\]的最优次序所包含的计算矩阵子链 A\[1:k\]和A\[k+1:n\]的次序也是最优的。  
计算量：A\[1:k\]的计算量加上A\[k+1:n\]的计算量，再加上A\[1:k\]和A\[k+1:n\]相乘的计算量  
**【方法】**  
设计算A\[i: j\]，1≤i≤j≤n，所需要的最少数乘次数m\[i, j\]，则原问题的最优值为m\[1,n\]  
当i=j时，A\[i: j\]=Ai，因此，m\[i, i\]=0，i=1,2,…,n  
当i<j 时，  
![在这里插入图片描述][202003251513237.png]  
可以递归地定义m\[i, j\]为：  
![在这里插入图片描述][20200325151355745.png]  
**【时间复杂度】** O ( n 2 ) O(n^2) O(n2)  
**【代码】**

#include<bits/stdc++.h>
    using namespace std;
    #define NUM 51
    int p[NUM],n;
    int m[NUM][NUM];
    int s[NUM][NUM];
    int main()
    { 
        cin>>n;
        for(int i=0; i<=n; i++)
            cin>>p[i];
        for(int r=2; r<=n; r++)
            for(int i=1; i<=n-r+1; i++)
            { 
                int j=i+r-1;//计算初值，从i处断开
                m[i][j] = m[i+1][j]+p[i-1]*p[i]*p[j];
                s[i][j] = i;
                for(int k=i+1; k<j; k++)
                { 
                    int t = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if (t < m[i][j])
                    { 
                        m[i][j] = t;
                        s[i][j] = k;
                    }
                }
            }
        cout<<m[1][n]<<endl;
        return 0;
    }

**递归算法：**

int Recurve(int i, int j)
    { 
        if(i==j)
            return 0;
        int u=Recurve(i, i)+Recurve(i+1,j)+p[i-1]*p[i]*p[j];
        s[i][j]=i;
        for(int k=i+1; k<j; k++)
        { 
            int t=Recurve(i, k)+Recurve(k+1,j)+p[i-1]*p[k]*p[j];
            if (t<u)
            { 
                u=t;
                s[i][j]=k;
            }
        }
        m[i][j]=u;
        return u;
    }

**备忘录算法：**  
与动态规划算法一样，备忘录方法用一个表格保存已解决的子问题的答案，再碰到该子问题时，只要简单地查看该子问题的解答，而不必重新求解。

int LookupChai  (int i, int j)
    { 
        if(m[i][j]>0)
            return m[i][j];
        if(i==j)
            return 0;
        int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];
        s[i][j]=i;
        for(int k=i+1; k<j; k++)
        { 
            int t=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];
            if (t<u)
            { 
                u=t;
                s[i][j]=k;
            }
        }
        m[i][j] = u;
        return u;
    }

**二、最长公共子序列**  
**【问题】**  
若给定序列X=\{x1,x2,…,xm\}，则另一序列Z=\{z1,z2,…,zk\}，是X的**子序列**是指存在一个严格递增下标序列\{i1,i2,…,ik\}使得对于所有j=1,2,…,k有：zj=xij。  
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的**公共子序列**。  
给定2个序列X=\{x1,x2,…,xm\}和Y=\{y1,y2,…,yn\}，找出X和Y的最长公共子序列。 并输出这个序列。  
**【分析】**  
设序列X=\{x1,x2,…,xm\}和Y=\{y1,y2,…,yn\}的最长公共子序列为Z=\{z1,z2,…,zk\} ，则  
1）若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。  
2）若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。  
3）若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。  
即：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]  
**【代码】**

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    char a[10010],b[10010];
    int dp[10010][10010],x[10010][10010];
    vector<char>v;
    
    void LCS(int i,int j)
    { 
        if(i==0||j==0)
            return;
        if(x[i][j]==1)
        { 
            LCS(i-1,j-1);
            v.push_back(a[i]);
        }
        else if (x[i][j]==2)
            LCS(i-1,j);
        else
            LCS(i,j-1);
    }
    
    int main()
    { 
        cin>>n>>m;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        for(int i=1; i<=m; i++)
            cin>>b[i];
        for(int i=1; i<=n; i++)
        { 
            for(int j=1; j<=m; j++)
            { 
                if(a[i]==b[j])
                { 
                    dp[i][j]=dp[i-1][j-1]+1;
                    x[i][j]=1;
                }
                else if (dp[i-1][j]>=dp[i][j-1])
                { 
                    dp[i][j]=dp[i-1][j];
                    x[i][j]=2;
                }
                else
                { 
                    dp[i][j]=dp[i][j-1];
                    x[i][j]=3;
                }
            }
        }
        cout<<dp[n][m]<<endl;
        LCS(n,m);
        for(int i=v.size()-1;i>=0;i--)
            cout<<v[i]<<" ";
        cout<<endl;
        return 0;
    }

**三、最大子段和**  
**【问题】**  
给定由n个整数（包含负整数）组成的序列a1,a2,…,an，求该序列子段和的最大值。  
当所有整数均为负值时定义其最大子段和为0。  
所求的最优值为：  
![在这里插入图片描述][2020032515561573.png]  
**【分析】**  
bj是1到j位置的最大子段和:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 1]  
由bj的定义易知，当bj-1>0时bj=bj-1+aj，否则bj=aj。  
则计算bj的动态规划递归式：bj=max\{bj-1+aj，aj\}，1≤j≤n。

**【代码】**

#include<bits/stdc++.h>
    using namespace std;
    
    int n,a[100010];
    int b,sum,l,r,s;
    
    int main()
    { 
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        for(int i=1; i<=n; i++)
        { 
            if(b>0)
                b+=a[i];
            else{ 
                b=a[i];
                s=i;
            }
            if(b>sum)
            { 
                sum=b;
                r=i;
                l=s;
            }
        }
        cout<<l<<" "<<r<<" "<<sum<<endl;
        return 0;
    }

**四、0-1背包问题**  
**【问题】**  
给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。  
如果物品不能被分割，即物品i要么整个地选取，要么不选取；不能将物品i装入背包多次，也不能只装入部分物品i，则该问题称为0—1背包问题。  
如果物品可以拆分，则问题称为背包问题，适合使用贪心算法。  
**【分析】**  
i≤k≤n的最优值为p(i，j)。  
是背包容量为j，可选物品为i，i＋1，…，n时0-1背包问题的最优值。  
![在这里插入图片描述][20200327144750736.png]  
![在这里插入图片描述][20200327144800697.png]  
![在这里插入图片描述][20200327144812301.png]  
**【代码】**

#include<bits/stdc++.h>
    using namespace std;
    int n,m;
    int f[100010],w[100010],v[100010];
    int main()
    { 
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>w[i]>>v[i];
        memset(f,0,sizeof(f));
        f[0]=0;
        for(int i=1; i<=n; i++)
            for(int j=m; j>=w[i]; j--)
                f[j]=max(f[j],f[j-w[i]]+v[i]);
        int ans=0;
        for(int j=0; j<=m; j++)
            ans=max(ans,f[j]);
        cout<<ans<<endl;
        return 0;
    }

[202003251513237.png]: /images/20230528/2444ddb9712f4073b65095d67e1a67fd.png
[20200325151355745.png]: /images/20230528/3404e57ae75e4c4a8e9946bde72776ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]: /images/20230528/37f0fc195faf487d983cc98ff42ecec7.png
[2020032515561573.png]: /images/20230528/eb6f282da51b4e08bcc3f0ac3132d383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70 1]: /images/20230528/c48feea9c6a04d53a67a0e36fed2141b.png
[20200327144750736.png]: /images/20230528/49b8f63332e945f99c6b9769ecbb5345.png
[20200327144800697.png]: /images/20230528/53b49f8a4b5c445daf606ff5bcf470ec.png
[20200327144812301.png]: /images/20230528/eb9acd03e18749d1b118eec3b653811e.png