基础算法：动态规划（一）

前言：

以前光憋算法题，但一直没弄清楚动态规划的使用方法。后来找了算法分析的黑书，但内容非常多，导致一直没时间看。最近在学习软件设计，教材里面对动态规划、贪心算法、回溯法这几种常见的基础算法进行了相当简洁的讲解，使我理解了许多，故此下笔。

这篇文章分为算法目标、适用条件、步骤设计、代码示例四个部分。

算法目标：

一般来说，是为了解决问题在有约束条件下的全局最优解。一个问题如果具有以下两个性质，就可以考虑使用动态规划法求解。

（1）最优子结构。即一个问题的最优解中包含了其子问题的最优解，或者说是由子问题的最优解构成。需要注意到的是，问题适用动态规划算法时也可能使用于贪心算法。

（2）重叠子问题。重叠子问题指的是用来解决原问题的递归算法可反复地解同样的子问题，而并不总是在产生新的子问题。相比于没有记忆的分治法在每次遇到相同子问题时都会视作一个新问题重新计算而言，动态规划自底向上计算，解决一个问题需要的子问题结果被保存在记录表中，随时可供使用，效率大大提高。

步骤设计：

使用动态规划解决这类问题，通常按照以下几个步骤进行：

（1）找出最优解的性质，并刻画其结构特征。

（2）递归地定义最优解的值。

（3）以自底向上的方式计算出最优值

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

例如经典的0-1背包问题，即是在背包容量有限的情况下，尽量往背包里装最高价值的物品。背包容量是约束条件，争取总价值最高是寻找问题的最优解。其中0-1指的物品只能有被整个装入或者不装两种状态，拿取物品的方案则可以看作一系列0和1的组合。以一个具体的例子来说明：

设背包初始容量W=30，则该问题可以形式化描述如下：

目标函数为$max(\sum _{i=1}^n{v}_i{x}_i)$$max(\sum_{i=1}^nv_ix_i)$

约束条件为$\sum _{i=1}^n{w}_i{x}_i\le W$$\sum_{i=1}^nw_ix_i \leq W$

该问题的求解过程可以看作是进行一系列的决策过程。假设背包容量为W，v_i和w_i分别表示第i个物品的价值和重量，x_i=1表示装入第i个物品。如果一个方案里的最优解包含了“装入物品n”，即x_n=1，则在选择物品1、2、...、n-1时，一定有容量为W-w_n的最优解。反之，最优解没有包含“装入物品n”，即x_n=0，则在选择物品1、2、...、n-1时，一定有容量为W的最优解。显然地，对每个物品的选择都适用于这个模式，都是全局问题的子问题。

根据上面的分析的最优解的结构可以递归的定义问题的最优解。设c[i,w]表示背包容量为w时选择物品i所导致的最优解的总价值，得到下式。

能看到，在物品i可以被装入背包时，我们通过比较装入和不装入后的总价值来确定是否该装入。

编写C代码

​x
1
#include <iostream>
2

3
using std::endl;
4
using std::cout;
5

6
int * selects = nullptr;
7
int ** diagram = nullptr; // 存储各选择下的最优解
8

9
// 打印选择
10
void printSelects(int * content,int n){
11
    cout << "selects:[";
12
    for(int i = 0; i < n; ++i){
13
        cout <<  content[i];
14
        if(i < n-1){
15
            cout << ",";
16
        }
17
    }
18
    cout << "]" << endl;
19
}
20

21
// 打印表格
22
void getDiagram(int W,int n){
23
    for (int i = 1 ; i <= n ; ++i){
24
        for (int j = 1 ; j <= W ; ++j){
25
            printf("%-4d",diagram[i][j]);
26
        }
27
        printf("\n");
28
    }
29
}
30

31
// 释放图的空间
32
void delDiagram(int ** diagram,int high){
33
    for(int i = 0; i < high ; i++){
34
        if(diagram[i]){
35
            delete [] diagram[i];
36
            diagram[i] = nullptr;
37
        }
38
    }
39
    delete [] diagram;
40
    diagram = nullptr;
41
}
42

43
// 算法主体,W反映的是装入的物品
44
int Bring(int * values,int * weights,int W,int n){
45
    // 自底向上填表
46
    for(int i = 1; i <= n ; ++i){
47
        for(int j = 1; j <= W ; ++j){
48
            if(weights[i-1] <= j ){
49

50
                if(diagram[i-1][j] > diagram[i-1][j-weights[i-1]]+values[i-1]){
51
                    diagram[i][j] = diagram[i-1][j];
52
                }
53
                else{
54
                    diagram[i][j] = diagram[i-1][j-weights[i-1]] + values[i-1];  // 装入物品i
55
                }
56

57
            }
58
            else{
59
                diagram[i][j] = diagram[i-1][j]; // 容量不够
60
            }
61
        }
62
    }
63
    return diagram[n][W];
64

65
}
66

67
// 因为动态规划是自底向上，填完表即结束算法，要得到装入物品的选择需要另写一个回溯算法
68
// 回溯得到装入物品的id
69
void getSelects(int * weights,int W,int n,int * selects){
70
    // 在相同容量下装入的物品就是最优解的选择之一
71
    while(W > 0 ){
72

73
        while(n > 0 && diagram[n][W] == diagram[n-1][W]){
74
            --n;
75
        }
76
        if(n == 0){
77
            break;
78
        }
79
        W -= weights[n-1];
80
        selects[--n] = 1;
81
    }
82
}
83

84

85

86
// 封装一下
87
void Resolve(int * values,int * weights,int W,int n){
88
    int Sum = 0; // 总价值
89

90
    selects = new int[n]{};  // 申请选择表并初始化
91

92
    diagram = new int *[n+1]{};  // 申请图并初始化
93
    for(int i = 0; i < n+1 ; ++i){
94
        diagram[i] = new int[W+1]{};
95
    }
96

97
    Sum = Bring(values,weights,W,n); // 调用
98
    getSelects(weights,W,n,selects);
99
    getDiagram(W,n);
100
    printSelects(selects,n); // 打印结果
101
    cout << "Sum:" << Sum << endl;
102

103
    delete [] selects;
104
    selects = nullptr;
105
    delDiagram(diagram,n+1);
106
}
107

108
int main(){
109
    int values[] = {3,4,7,8,9,10,11}; // 物品价值
110
    int weights[] = {4,5,10,11,13,14,17}; // 物品重量
111
    int W = 30;  // 背包容量
112

113
    Resolve(values,weights,W,sizeof(weights)/sizeof(int));
114
    return 0;
115
}
116

编写Python代码

xxxxxxxxxx
41
1
def Resolve(values,weights,W,n):
2
    diagram = []
3
    # 初始化表格
4
    for i in range(n+1):
5
        diagram.append([0]*(W+1))
6

7
    #填表
8
    for i in range(1,n+1):
9
        for j in range(1,W+1):
10
            if j >= weights[i-1] :
11
                if diagram[i-1][j] > (diagram[i-1][j-weights[i-1]] + values[i-1]):
12
                    diagram[i][j] = diagram[i-1][j]
13
                else:
14
                    diagram[i][j] = diagram[i-1][j-weights[i-1]] + values[i-1]
15
            else:
16
                diagram[i][j] = diagram[i-1][j]
17

18
    # get装入选择
19
    selects = [0]*n
20
    def getSelects(W,n):
21
        while(W > 0):
22
            while((n>0) and (diagram[n][W] == diagram[n-1][W])):
23
                n -= 1
24
                
25
            if not n > 0:
26
                break  
27
            W -= weights[n-1]
28
            selects[n-1] = 1
29
            n -= 1
30

31
    getSelects(W,n)
32

33
    #打印结果
34
    print("selects: " + str(selects))
35
    print("sum: {}".format(diagram[n][W]))
36

37
if __name__ == "__main__":
38
    values = [3,4,7,8,9,10,11]
39
    weights = [4,5,10,11,13,14,17]
40
    W = 30
41
    Resolve(values,weights,W,len(weights))

结果如图：

xxxxxxxxxx
2
1
selects:[1,1,1,1,0,0,0]
2
Sum:22