动态规划分析步骤与代码（背包、最大公共子串）

发表于 | 分类于 | 阅读次数: |

前言

动态规划在《数据结构与算法》中接触过，随后在《软件设计师教程》中也学习过，每次学完没有做记录，感觉会了，但实际上还是有些不理解的。这次在《图解算法》中重新接触到动态规划，讲得挺透彻的，应该要好好记录下来。无论动态规划的问题有多么形式多样，只要了解了解题思路和原理。再多加练习，肯定能掌握的。

基本思想

其基本思想是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

这是《软件设计师教程》中对动态规划思想的描述。看起来很简单，就把大问题划成小问题。恰恰难的也就是如何将大问题化解成小问题。通过这篇文章，来慢慢体会这个划分的过程。

经典背包问题

背包
背包可以装 4 磅；
音响 3000元，4磅；
笔记本电脑，2000元，3磅；
吉他，1500元，1磅。
书中是直接提供的自底向上解题的过程。
在这里我们先从上至下分析一下问题：

拿还是不拿？

对于每一个物品，我们都有两个选择，拿或者不拿。我们需要解决的是：拿哪些能达到最高价值？

现在我们什么都没拿，0价值，4磅空间。我们先考虑吉他：

拿吉他：现在背包价值1500，剩余空间3磅。
不拿吉他：背包价值0，剩余空间4磅。

然后在拿或不拿的基础上考虑音响，
拿了吉他，价值1500元，剩余3磅空间：

拿音响：音响占用空间4磅 > 剩余空间3磅，所以拿不下。现在背包价值1500，剩余3磅空间。
不拿音响：和原来一样，背包价值1500，剩余空间3磅。

不拿吉他，价值0元，剩余4磅空间：

拿音响：背包价值3000，剩余0空间。
不拿音响：背包价值0，剩余4空间。

然后在前两者组合的基础上再考虑笔记本电脑，
其中组合为：

1.拿了吉他，拿不下音响：剩余3空间
2.拿了吉他，不拿音响：剩余3空间
3.没拿吉他，拿音响：剩余0空间
4.没拿吉他，也没拿音响：剩余4空间

我们发现，1和2剩余的3磅空间刚好再拿个笔记本电脑，且1组合价值最高，而4组合仅拿了电脑，价值为2000，不如1组合。
似乎到这里我们仍然得不到什么结论，以上的方法，类似一个排列组合，查看所有的组合方式中的最高价值。但是我们却已经完成了 背包问题的第一步：刻画最优子结构

拿了某物品，和剩下空间的最优解
不拿某物品，和剩下空间的最优解

一点一点挤

我们完成了从上到下的分析，子问题是在剩下的空间里选择最值钱的物品。然后考虑第二步：合并子问题，也就是自下而上合并。

假如剩下1空间，我们拿什么最划算？
假如剩下2空间，我们拿什么最划算？
……

因此我们需要画一个表格用来记录子问题的最优解：

行：当前行和之前行表示可以选择的物品
列：表示背包的剩余空间

因为我们考虑的是剩余空间，因此填充列：
剩余空间1：很明显，剩余空间1时，我们只能拿吉他，因此在第一列，我们填入吉他与价格：

1 2 3 4
吉他（G） 1500 （G）
音响（S） 1500 （G）
笔记本 (C) 1500 （G）

剩余空间2：我们仍然不能拿其他的物品，因此在第二列，我们填入吉他与价格：

1 2 3 4
吉他（G） 1500 （G） 1500 （G）
音响（S） 1500 （G） 1500 （G）
笔记本 (C) 1500 （G） 1500 （G）

剩余空间3：在这里，我们发现，当遇到笔记本电脑时，可以装下而且比吉他价格高，因此我们在笔记本行填入笔记本：

1 2 3 4
吉他（G） 1500 （G） 1500 （G） 1500 （G）
音响（S） 1500 （G） 1500 （G） 1500 （G）
笔记本 (C) 1500 （G） 1500 （G） 2000 （C）

剩余空间4：在这里我们又发现，遇到音响时，可以装下，且价格为3000：

1 2 3 4
吉他（G） 1500 （G） 1500 （G） 1500 （G） 1500 （G）
音响（S） 1500 （G） 1500 （G） 1500 （G） 3000 （S）
笔记本 (C) 1500 （G） 1500 （G） 2000 （C）

最后一格怎么办呢，现在最大价格是3000，如果拿电脑，就装不下音响，价值只有2000，价值没有之前高。但 如果拿电脑，背包则还可以装1空间的物品。因此我们看看空间剩1时，可以装的最高价格是什么东西。我们之前表中已经填过，是吉他。且笔记本+吉他的价格为3500，超过了音响的价格。所以我们在最后一格中填入

1 2 3 4
吉他（G） 1500 （G） 1500 （G） 1500 （G） 1500 （G）
音响（S） 1500 （G） 1500 （G） 1500 （G） 3000 （S）
笔记本 (C) 1500 （G） 1500 （G） 2000 （C） 3500（C/G）

在这里我们发现，如果可选择的物品重量大于剩余空间时，是不能放入背包的。而当前可选物品可以放进去时，就需要进行比较。那么，是比较什么呢？至此，我们可以得到计算剩余空间最大价值的公式 ：

因为当前行是需要选择是否拿的物品，所以使用上一行的值作为参照。

比如第三行3列：笔记本，剩余空间3时，就要选择比较：

拿：放下吉他，价值2000，剩余空间0
不拿：价值1500，剩余空间3

显而易见，拿比不拿价格高。

音响同理；

在比如第三行3列：笔记本，剩余空间4时，选择比较如下：

拿：放下音响，价值2000，剩余空间1。还可以拿吉他，一共价值3500
不拿：价值3000，剩余空间0

显而易见，拿比不拿价格高。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
//填表计算 最优解
int** KnapsackDP(int n,int W,int* weights,int* values)
{
    int i,w;
    //因为数组下标是从0开始且需要用上一行做基础，所以 n+1 ， w + 1
    int **c = (int **)malloc(sizeof(int *) * (n+1));
    for(i=0; i<=n; i++)
    {
        c[i]=(int *)malloc(sizeof(int)*(W+1));

        //初始化所有格子为0
        for(w = 0 ; w<=W ; w++)
            c[i][w] = 0;
    }
    //从最小空间开始
    for(w= 1 ; w <= W ; w++)
    {   //所有物品
        for(i = 1 ; i<=n ; i++)
        	//判断当前物品是否放得下
            if(weights[i-1] <= w)
            {	
            	//比较放和不放的价值
                if(values[i-1] + c[i-1][w - weights[i-1]] > c[i-1][w])
                	//放，价值为当前物品的价值加上剩余空间的最大价值
                    c[i][w] = values[i-1] + c[i-1][w-weights[i-1]];
                else
                    c[i][w] = c[i-1][w];
            }
            else
            {  //放不下，直接沿用之前的
                c[i][w] = c[i-1][w];
            }


    }
    return c;
}

//根据最优解值找最优解序列
void OutputKnapsackDP(int n,int W , int* Weights,int *Values, int **c){
    int x[n];
    int i;
    for(i = n ; i > 1 ; i--){
        if(c[i][W] == c[i-1][W])  //判断是否包含该物品
            x[i-1] =0;
        else {
            x[i-1] = 1;
            W = W- Weights[i-1];   //包含，修改背包容量
        }
    }
    if(c[1][W] == 0)  //判断第一个物品是否放入
        x[0] = 0;
    else
    x[0] = 1;
    for(i = 0 ; i< n ; i ++){
        if(x[i])
            printf("Weight:%d , Value %d\n",Weights[i],Values[i]);
    }

}

int main()
{
    int n = 3,w = 4;
    int weights[4] = {1,4,3};
    int values[4]= {1500,3000,2000};
    int** c;
    int i,j;
    c = KnapsackDP(n,w,weights,values);
    for(i = 0 ; i <= n ; i ++)
    {
        for(j = 0 ; j <= w  ; j++)
        {
            printf("%d ", c[i][j]);
        }
        printf("\n");
    }
    printf("打印最优结构\n");
    OutputKnapsackDP(n,w,weights,values,c);

    return 0;
}

运行结果如下：
运行结果

最长公共子序列

《软件设计师教程》中的描述：

子序列是指从给定序列中随意地(不一定是连续的)去掉若干元素后所形成的序列。如X = ABCBDAB , Y = BCDB，则Y是X的一个子序列。若给定两个X和Y，如果Z同时是X和Y的子序列，那称Z是X和Y的公共子序列。最长公共子序列问题定义为：给定序列X和Y，求这两个序列的最长公共子序列。

有点抽象化，所以看起来很费劲，那看一下《图解算法》的例子:
exm
那我们怎么猜用户应该输入的是什么呢？
是fish？
还是vista？

当然是看和哪个单词重合度更高一点，因此我们便采用最长公共序列算法。

谁和谁一样

使用fish和hish不太能体现最长序列的分析，我们采用软考教程的例子：

X = ABCBDAB
Y = BDCABA

人工判断的话，自然是先在两个序列中找到第一个相等的，记下来

AB & B -> B

然后再往后找第二个一样的

C & DC -> C
也就是 ABC & BDC - > BC

继续

B & AB -> B
也就是 ABCB & BDCAB -> BCB

然后

DA & A -> A
也就是 ABCBDA & BDCABA -> BCBA

Y序列已经没有字符了，所以我们也就找完了。可以发现，后面被寻找的内容都是在前面找到的相等的字母后面，也就是说CBDA & DCABA - > CBA 。都去除一个相同的字母结尾的序列，剩下的公共子串也是其剩余序列的最长公共子串。

一个一个比

那计算机应该怎么进行比较呢，它不能像人一样一次比较多个字母，也不知道何时两个字母会相等。所以就要一个一个字母进行比较，同时记录比较情况。

X = FISH
Y = HISH

F I S H
H
I
S
H

这个表记录的就是子字符串的公共子串字母个数。
按行进行分析
第一行，H 分别与 F 、 FI 、 FIS 、 FISH 的最大子串
第二行，HI 分别与 F 、 FI 、 FIS 、 FISH 的最大子串
第三行，HIS 分别与 F 、 FI 、 FIS 、 FISH 的最大子串
第四行，HISH 分别与 F 、 FI 、 FIS 、 FISH 的最大子串

按照之前分析的，如果字母相等的话，就去掉相同字母的最长公共子串 + 1 。在不相等的情况下，则需要判断去掉比较双方的其中一个之后哪一个的 值比较大，以记录最长的公共子串。

如

HI & FI : I 相等，那就 H & F（去掉比较字符I ）的最长公共子串值 0 + 1 。
HI & FIS : I 不等于 S , 选择 HI & FI （去掉 S） 的值 1 与 H & FIS （去掉 I）的值 0 中较大的一个。

依次类推得到下表：

F I S H
H 0 0 0 1
I 0 1 1 1
S 0 1 2 2
H 0 1 2 3

这里我们知道了最终结果的值是3，但是好像看不出来公共子串的序列是什么。所以我们需要记录序列路径。

上表示 去掉比较的行字符 比 去掉比较的列字符 更大

左表示 去掉比较的列字符 比 去掉比较的行字符 更大

左上表示 比较字符相等，去掉比较字符之后 + 1

x F I S H
y 0 0 0 0 0
H 0 0 ↑ 0 ↑ 0 ↑ 1 ↖
I 0 0 ↑ 1 ↖ 1 ← 1 ↑
S 0 0 ↑ 1 ↑ 2 ↖ 2 ←
H 0 0 ↑ 1 ↑ 2 ↑ 3 ↖

这时我们便可以看到，从 H -> S -> I 逆序过来就是最长公共子序列的字母了。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/**
* 求出最长序列
*/
int** Lcs_Lenth(const char * str1, const char * str2, int str1_length, int str2_length)
{
    int i,j;
    //记录最长序列
    int **l= (int **)malloc(sizeof(int *) * (str1_length + 1));
    //记录序列导向
    int **b= (int **)malloc(sizeof(int *) * (str1_length + 1));

    //分配空间
    for(i = 0 ; i <= str1_length ; i ++)
    {
        l[i] = (int *) malloc( sizeof(int *) * str2_length + 1) ;
        b[i] = (int *) malloc( sizeof(int *) * str2_length + 1) ;

        for(j = 0 ; j <= str2_length ; j ++)
        {
            l[i][j] = 0 ;
            b[i][j] = -1;
        }
    }

    //依次比较
    for(i = 1 ; i <= str1_length ; i++)
        for( j = 1 ; j<=str2_length ; j++)
        {
            //相等
            if(str1[i-1] == str2[j-1])
            {
                l[i][j] = l[i-1][j-1] + 1;  //去掉相同字母，i-1，j-1;
                b[i][j] = 0 ;   //代表左上
            }
            else if(l[i-1][j] >= l[i][j-1])  //去掉行比较字母比较大
            {
                l[i][j] = l[i-1][j];    //行级  i - 1
                b[i][j] = 1;           //代表上方
            }
            else
            {
                l[i][j] = l[i][j-1];  //列级 j - 1
                b[i][j] = 2;    //代表 右方
            }

        }
    printf("输出长度\n");

    for(i = 0 ; i <= str1_length ; i++)
    {
        for( j = 0 ; j<=str2_length ; j++)
        {
            printf("%d ", l[i][j]);
        }
        printf("\n");
    }

    printf("输出导向\n");

    for(i = 0 ; i <= str1_length ; i++)
    {
        for( j = 0 ; j<=str2_length ; j++)
        {
            switch(b[i][j]){
            case 0: printf("↖"); break;
            case 1: printf("↑"); break;
            case 2: printf("←"); break;
            default : printf("0 ");
            }
        }
        printf("\n");
    }
    return b;
}

//递归输出公共子序列序列
void OutputLcs(const char *str1, const int **b, int str1_length, int str2_length )
{
    //直到一个字符串比较完毕
    if(str1_length ==0 || str2_length ==0)
        return ;
    //表示两个字符相等
    if(b[str1_length][str2_length] == 0)
    {   //去掉该字符
        OutputLcs(str1,b,str1_length-1, str2_length - 1 );
        printf("%c",str1[str1_length - 1]);
    }
    //表示去掉行级比较大
    else if(b[str1_length][str2_length] == 1)
    {   //去掉其中一个比较字符
        OutputLcs(str1,b,str1_length - 1,str2_length);
    }
    else
    {   //去掉另外一个
        OutputLcs(str1,b,str1_length,str2_length - 1);
    }
}

int main()
{
    char* str1 = "ABCBDAB";
    char* str2 = "BDCABA";
    int** b =Lcs_Lenth(str1,str2,strlen(str1),strlen(str2));
    printf("输出序列\n");
    OutputLcs(str1,b,strlen(str1),strlen(str2));
    return 0;
}

结果如下

res

总结

  • 动态规划解决的是问题具有最优子结构，总问题的解可以由子问题的解合并得来
  • 子问题具有重叠性，有许多的子问题是重复的
  • 采用填表法，即记录子问题的解不再重复结算