动态规划和贪心算法是常见的分治策略,将问题分解成若干规模较小的相同问题,通过合并求解相对容易的子问题得到原问题的解。

一、最长公共子序列(LCS)
给定两个字符序列,不要求所求的字符序列在所给的字符串中是连续的,求解最大公共序列。
设序列X=<x0,x1,x2,...xm>和Y=<y0,y1,y2,...yn>,最长子序列为Z=<z0,z1,z2,...,zk>
(1)xm==yn,必然有xm==yn==zk,<z0,z1,z2,...,zk-1>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn-1>的子序列;
(2)xm!=yn且xm!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm-1>和<y0,y1,y2,...yn>的子序列;
(3)xm!=yn且ym!=zk,<z0,z1,z2,...,zk>是<x0,x1,x2,...xm>和<y0,y1,y2,...yn-1>的子序列;
即:
LCS(Xm,Yn)=LCS(Xm-1,Yn-1),当xm==yn;
LCS(Xm,Yn)=max{LCS(Xm-1,Yn),LCS(Xm,Yn-1)},当xm!=yn;
转化为递推式:
3.jpg

接下来很方便的使用动态规划方法(自底而上)逐步求解原问题,注意到LCS[0,i]=LCS[i,0]=0,LCS[0,0]=0.

int c[100][100];
int LCS_LENGTH(const char *X,const char*Y)
{
    if(X==NULL||Y==NULL)
        return 0;
    int m=strlen(X);
    int n-strlen(Y);
    for(int i=0;i<=n;i++)
        c[0][i]=0;
    for(int i=0;i<=m;i++)
        c[i][0]=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(X[i]==X[j])
                c[i,j]=c[i-1,j-1]+1;
            else
                c[i,j]=(c[i-1][j]>c[i][j-1]?c[i-1][j]:c[i][j-1]);
        }
    return c[m][n];
}

动态规划有一种变形,既具有动态规划效率,同时自顶而下求解,使用备忘录维护子问题的解从而避免重复的递归求解。

#define INF 999999
int c[100][100];
int LCS_LENGTH(const char *X,const char*Y,int i,int j)
{
    if(c[i][j]<INF)
        return c[i][j];
    if(i==0||j==0)
        return 0;
    else if(x[i-1]==Y[j-1])
        c[i][j]=LCS_LENGTH(X,Y,i-1,j-1)+1;
    else
    {
        int p=LCS_LENGTH(X,Y,i-1,j);
        int q=LCS_LENGTH(X,Y,i,j-1);
        if(p>q)
            c[i][j]=p;
        else
            c[i][j]=q;
    }
}
int main()
{
    int m=strlen(X);
    int n-strlen(Y);
    memset(c,INF,sizeof(c));
    int max=LCS_LENGTH(X,Y,m,n);
}


二、0-1背包问题 & 部分背包问题
(1)0-1背包问题:有n件物品和一个可盛重量为w的背包。第i件物品的价值是v[i],重w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包可盛重量,且价值总和最大。这个问题的特点是:每种物品只有一件,可以选择放或者不放。
(2)部分背包问题:场景和上面类似,不同的是可以带走部分商品,可以将黄金想象成金粉。

两个问题非常类似,部分背包问题可以使用贪心算法,而0-1背包问题不可以。每个商品的单位价值为v[i]/w[i],部分背包问题的求解原则是先拿单位价值最大的商品,拿完后再选择单位价值次大的商品...。0-1背包问题却不可以这样做,如果先选取单位价值最大的商品,导致背包空间不能充分利用,往往不能产生最优解。我们可以使用动态规划来来求解0-1背包问题:
假设v[i]、w[i]分别表示第i件商品的价值和重量,fi表示背包重量为j时,可选商品1~i时的最大价值,状态转移方程如下:
4.jpg

其中,j<w[i]表示第i件商品装不下,从而原问题退化为fi-1;第二种情况
(1)第i件商品不放
(2)第i件商品放入,可放商品减少到i-1,可用重量减少到j-w[i],价值增大v[i]
上面(1)(2)的最大值为fi。

对应动态规划代码如下:

int N=3,V=5; // N商品数目,V背包重量
int w[4]={0,1,2,3};
int V[4]={0,60,100,120};
for(int i=0;i<=V;i++)
    f[0][j]=0;
for(int i=0;i<=N;i++)
{
    f[i][0]=0;
    for(int j=1;j<=V;j++)
        if(j<w[j])
            f[i][j]=f[i-1][j];
        else
            f[i][j]=(f[i-1][j]>f[i-1][j-w[i]]+w[i]?f[i-1][j]:f[i-1][j-w[i]]+w[i]);
}

...

标签: 动态规划, 贪心算法

评论已关闭