算法设计与分析-动态规划

  动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

  划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
  确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
  确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
  寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。一般地，只要问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

  实际应用中可以按以下几个简化的步骤进行设计：

  (1) 分析最优解的性质，并刻画其结构特征。
  (2) 递归的定义最优解。
  (3) 以自底向上或自顶向下的记忆化方式计算出最优值。
  (4) 根据计算最优值时得到的信息，构造问题的最优解。

求解整数拆分问题

  求将正整数$n$无序拆分成最大数为$k$的拆分数，要求所有的拆分方案不重复。

  问题求解：设$n = 5$，$k = 5$，对应的拆分方案有：

  $5 = 5$
  $5 = 4 + 1$
  $5 = 3 + 2$
  $5 = 3 + 1 + 1$
  $5 = 2 + 2 + 1$
  $5 = 2 + 1 + 1 + 1$
  $5 = 1 + 1 + 1 + 1 + 1$

  为了防止重复计数，让拆分数保持从大到小排序，正整数$5$的拆分数为$7$。

  显然将正整数$n$无序拆分成最大数为$k$的拆分数，与将整数$n$拆分成最多不超过$k$个数之和的拆分数相等。

  采用动态规划求解整数拆分问题。设$dp(n, k)$为将数$n$无序拆分为最多不超过$k$个数之和的拆分数：

  (1) 当$n = 1$，$k = 1$时，显然$dp(n, k) = 1$。

  (2) 当$n < k$时，有$dp(n, k) = dp(n, n)$。

  (3) 当$n = k$时，其拆分方案包含将正整数$n$无序拆分成最大数为$n - 1$的拆分方案，另一种拆分方案是将$n$拆分成$n$个$1$，所以有$dp(n, n) = dp(n, n - 1) + 1$。

  (4) 当$n > k$时，拆分方案有两种情况，正整数$n$无序拆分为最大数为$k - 1$的拆分方案，此时的拆分方案数为$dp(n, k - 1)$，另一种情况是，余下的数无序拆分为正好$k$个数之和，此时的拆分方案数为$dp(n - k, k)$，所以有：$dp(n, k) = dp(n, k - 1) + dp(n - k, k)$。（方案3是方案4的特例）

  对应的递归算法如下：

1
2
3
4
5
6
7
8
9
10
11
int dpf(int n, int k)
{
    if (n == 1 || k == 1)
        return 1;
    else if (n < k)
        return dpf(n, n);
    else if (n == k)
        return dpf(n, k - 1) + 1;
    else
        return dpf(n, k - 1) + dpf(n - k, k);
}

  由于$n$，$k$均为正整数，可以用一个二维数组$dp$来存放将正整数$n$无序拆分成最大数为$k$的拆分数，$dp[n][k]$即为所求结果。采用递推方式实现对应的非递归算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dp[MAXN][MAXN];

void split(int n, int k)
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= k; j ++)
        {
            if (i == 1 || j == 1)
                dp[i][j] = 1;
            else if (i < j)
                dp[i][j] = dp[i][i];
            else if (i == j)
                dp[i][j] = dp[i][j - 1] + 1;
            else if (i > j)
                dp[i][j] = dp[i][j - 1] + dp[i - j][j];
        }
}

求解最大连续子序列和问题

  问题求解：对于含有$n$个整数的序列$a$，设$b_j$（$1 \leqslant j \leqslant n$）表示前$j$个元素$a_1 \sim a_j$中的以$a_j$结尾的最大连续子序列和，显然，当$b_{j - 1} > 0$时，$b_j = b_{j - 1} + a_j$，当$b_{j - 1} \leqslant 0$时，放弃前面选取的元素，从$a_j$开始重新选起，$b_j = a_j$。

  所以采用动态规划的顺序法可得到$b_j$的递推式为：

  $b_0 = 0$，$j = 0$，边界条件。

  $b_j = max\{b_{j - 1} + a_j, a_j\}$，$1 \leqslant j \leqslant n$。

  序列$a$的最大连续子序列和等于$b_j$（$1 \leqslant j \leqslant n$）中的最大者。

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
void MaxSubSum(int a[], int b[], int n)
{
    int j;
    b[0] = 0;
    for (j = 1; j <= n; j++)
    {
        if (b[j - 1] + a[j] > a[j])
            b[j] = b[j - 1] + a[j];
        else
            b[j] = a[j];
    }
}

void dispMaxSum(int a[], int b[], int n)
{
    int maxj, i, j, k;
    maxj = 1;
    for (j = 2; j <= n; j++)
        if (b[j] > b[maxj])
            maxj = j;
    for (k = maxk; k >= 1; k--)
        if (b[k] <= 0)
            break;
    printf("最大连续子序列和：%d", b[maxj]);
    printf("所选子序列：")；
    for (i = k + 1; i <= maxj; i++)
        printf("%d ", a[i]);
    printf("\n");
}

求解最长公共子序列问题

  字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。

  给定两个序列$A$和$B$，称序列$Z$是$A$和$B$的公共子序列，是指$Z$同是$A$和$B$的子序列。

  该问题是求两序列$A$和$B$的最长公共子序列（$Longest Common Subsequence$，简称为$LCS$）。

  问题求解：考虑最长公共子序列问题如何分解成子问题，设$A = (a_0, a_1, \dots , a_{m - 1})$，$B = (b_0, b_1, \dots , b_{n - 1})$，设$Z = (z_0, z_1, \dots , z_{k - 1})$为它们的最长公共子序列。不难证明有以下性质：

  (1) 如果$a_{m - 1} = b_{n - 1}$，则$z_{k - 1} = a_{m - 1} = b_{n - 1}$，且$(z_0, z_1, \dots , z_{k - 2})$是$(a_0, a_1, \dots , a_{m - 2})$和$(b_0, b_1, \dots , b_{n - 2})$的一个最长公共子序列；

  (2) 如果$a_{m - 1} \neq b_{n - 1}$且$z_{k - 1} \neq a_{m - 1}$，蕴涵$(z_0, z_1, \dots , z_{k - 1})$是$(a_0, a_1, \dots , a_{m - 2})$和$(b_0, b_1, \dots , b_{n - 1})$的一个最长公共子序列；

  (3) 如果$a_{m - 1} \neq b_{n - 1}$且$z_{k - 1} \neq b_{n - 1}$，蕴涵$(z_0, z_1, \dots , z_{k - 1})$是$(a_0, a_1, \dots , a_{m - 1})$和$(b_0, b_1, \dots , b_{n - 2})$的一个最长公共子序列。

  定义$c[i][j]$为序列$(a_0, a_1, \dots , a_{i - 1})$和$(b_0, b_1, \dots , b_{j - 1})$的最长公共子序列的长度，采用动态规划法，每考虑一个字符$a[i]$或$b[j]$都为动态规划的一个阶段（共经历约$m \times n$个阶段）。计算$c[i][j]$可递归地表述如下：

  (1) $c[i][j] = 0$，如果$i = 0$或$j = 0$。

  (2) $c[i][j] = c[i - 1][j - 1] + 1$，如果$i, j > 0$且$a[i - 1] = b[j - 1]$。

  (3) $c[i][j] = max(c[i][j - 1], c[i - 1][j])$，如果$i, j > 0$且$a[i - 1] \neq b[j - 1]$。

  从上述$3$种情况看到，对于$c[i][j]$，仅当情况(2)成立时表示$a[i - 1] = b[j - 1]$，此时$a[i - 1]$属于最长公共子序列的元素。设最长公共子序列长度为$k$，用$s[0 \dots k - 1]$存放最长公共子序列，求$k$的过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s[k] = '\0';  // 先在s中添加一个串结束符
while (k > 0)
{
    if (c[i][j] == c[i - 1][j])
        i--;
    else if (c[i][j] == c[i][j - 1])
        j--;
    else
    {
        s[--k] = a[i - 1];
        i--;
        j--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int LCSLength(char* a, char* b, int c[][N])
// 求最长公共子序列的长度
{
    int m = strlen(a), n = strlen(b);
    int i, j;
    for (i = 0; i <= m; i++)
        c[i][0] = 0;
    for (i = 0; i <= n; i++)
        c[0][i] = 0;
    for (i = 1; i < m; i++)
        for (j = 1; j < n; j++)
        {
            if (a[i - 1] == b[j - 1])
                c[i][j] = c[i - 1][j - 1] + 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[m][n];
}

求解0/1背包问题

  问题求解：对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即$max\{v_1 \times x_1 + v_2 \times x_2 + \dots + v_i \times x_i\}$，其中$1 < i < n$，$x_i$取$0$或$1$，取$1$表示选取物品$i$。

  在该问题中需要决定$x_1, x_2, \dots , x_n$的值。假设按$i = 1, 2, \dots , n$的次序来确定$x_i$的值，共有$n$次决策即$n$个阶段，第$k$阶段装入物品$k$，其状态变量为$s_k$，决策变量为$x_k$，状态转移方程为$s_k = s_{k - 1} + w_{k - 1}x_{k - 1}$。

  如果置$x_1 = 0$，则问题转变为相对于其余物品（即物品$2, 3, \dots , n$），背包容量仍为$W$的背包问题。若置$x_1 = 1$，问题就变为关于最大背包容量为$W - w_1$的问题。

  在决策$x_i$时，问题处于以下两种状态：

  (1) 背包中不能装下物品$i$，则$x_i = 0$，背包不增加重量和价值，背包余下容量$r$不变。

  (2) 背包中可以装下物品$i$，则$x_i = 1$，背包中增加重量$w_i$和价值$v_i$，背包余下容量$r = r - w_i$。

  假设$f(i, r)$表示背包剩余容量为$r$（$1 \leqslant r \leqslant W$），已考虑物品$1, 2, \dots, i$（$1 \leqslant i \leqslant n$）时的最优解的值，即利用最优序列由最优子序列构成的结论。采用动态规划的顺序法可得到$f(i, r)$的递推式为：

  $f(i, r) = f(i - 1, r)$，当$r < w_i$时，物品$i$放不下。

  $f(i, r) = max\{f(i - 1, r), f(i - 1, r - w_i) + v_i\}$，当$r \geqslant w_i$，在放入和不放入物品$i$之间选最优解。

  其边界条件为：

  $f(i, 0) = 0$，背包不能装入任何物品时，总价值为$0$。

  $f(0, r) = 0$，没有任何物品可装入时，总价值为$0$。

  这样，$f(n, W)$便是背包问题的最优解。

  当$f$值确定后，推导出$x$的过程十分简单，若$f(i, r) \neq f(i - 1, r)$，此时一定有$f(i, r) > f(i - 1, r)$，表示表示选取了物品$i$，对应的$x_i$置为$1$，否则没有选取物品$i$，对应的$x_i$置为$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
int Knap(int f[MAXN][MAXW], int w[], int v[], int W, int n)
{
    int i, r;
    for (i = 0; i <= n; i++)
        f[i][0] = 0;
    for (r = 0; r <= W; r++)
        f[0][r] = 0;
    for (i = 1; i <= n; i++)
        for (r = 1; r <= W; r++)
            if (r < w[i])
                f[i][r] = f[i - 1][r];
            else
                if (f[i - 1][r] < f[i - 1][r - w[i]] + v[i])
                    f[i][r] = f[i - 1][r - w[i]] + v[i];
                else
                    f[i][r] = f[i - 1][r];
    return f[n][W];
}

int TraceBack(int f[MAXN][MAXW], int w[], int v[], int x[], int W, int n)
{
    int i, r = W;
    int maxw = 0;
    for (i = n; i > 0; i--)
        if (f[i][r] != f[i - 1][r])
        {
            x[i] = 1;
            maxw += w[i];
            r -= w[i];
        }
        else
            x[i] = 0;
    return maxw;
}

求解资源分配问题

  某公司有$A, B, C$三个商店，拟将新招聘的$5$名员工分配给这三个商店，各商店得到新员工后，每年的赢利情况如下表所示，求分配给各商店各多少员工才能使公司的赢利最大？

0 1 2 3 4 5
A 0 3 7 9 12 13
B 0 5 10 11 11 11
C 0 4 6 11 12 12

  问题求解：按$A, B, C$商店进行决策，加上一个虚拟阶段，阶段数为$K = 4$。

  设总员工数为$S$（这里$S = 5$），用$s_k$表示给第$k$（$1 \leqslant k \leqslant K$）个商店分配员工时的状态变量，$d[k][s_k]$表示在状态$s_k$下分配给第$k$个商店的员工数，即决策变量，并有$s_{k + 1} = s_k - d[k][s_k]$（状态转移方程）。

  用$v[k][s_k]$表示给第$k$个商店分配$d[k][s_k]$人后所得到的赢利值。设$f_k(s_k)$表示在分配到第$k$个商店还有未分配人数$s_k$的情况下，分配完所有人员时公司所能获得的最大赢利，采用动态规划递序法可以得到如下递推式：

  $f(s_4) = 0$，$0 \leqslant s_4 \leqslant S$

  $f_k(s_k) = \underset{0 \leqslant x_k \leqslant s_k}{max}\{v[k][x_k] + f_{k + 1}(s_k - x_k)\}$，$k = 3, 2, 1$

  显然$f_1(S)$即为最大的赢利值，对应的$d[1][S]$为第$1$阶段最优分配的人数。

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
int Plan(int v[][MAXS], int d[][MAXS], int K, int S)
{
    int x, s, k;
    int maxf;
    for (s = 0; s <= S; s++)
        f[K][s] = 0;
    for (k = K - 1; k >= 1; k--)
        for (s = 0; s <= S; s++)
        {
            maxf = 0;
            for (x = 0; x <= s; x++)
            {
                if ((v[k][x] + f[k + 1][s - x]) >= maxf)
                {
                    maxf = v[k][x] + f[k + 1][s - x];
                    d[k][s] = x;
                }
            }
            f[k][s] = maxf;
        }
    return f[1][S];
}

void dispplan(int max, int d[][MAXS], int K, int S)
{
    int k, r, s;
    s = d[1][S];
    r = S - s;
    printf("最优资源分配方案如下：\n");
    for (k = 1; k < K; k++)
    {
        printf(" %c商店分配%d人\n", 'A' + k - 1, s);
        s = d[k + 1][r];
        r = r - s;
    }
    printf("该分配方案的总盈利为%d万元\n", max);
}