第 3 章 记表备查

第 3 章 记表备查动态规划

1.最优子结构 组合优化问题，指的是问题有多个可行解， 每一个可行解对应一个目标值，目的是要 在可行解中求得目标值最优者(最大或最 小)。 最优子结构特性指的是问题的最优解包含 的子问题的解相对于子问题而言也是最优 的。

2.子问题重叠 问题的一个递归算法在每个递归步骤产生 分支子问题时并不总是新的，而是对部分 子问题解了又解。当一个递归算法一次又 一次地访问同一个子问题时，我们说该最 优化问题具有重叠子问题的特性。

动态规划 针对具有上述两个特征的优化问题，动态规划算 法通常需要做如下的3步工作： (1)利用最优子结构定义一个关于解的目标值的 递归方程。鉴于子问题的重叠性，如果自顶向下 地用递归技术解每一个遇到的子问题，则可能陷 入一个“时间黑洞”。 (2)因此，动态规划以自底向上地对每个新产生 的子问题仅解一次且将其解保存在一个表格中， 需要时可以在表中查找，且能在常数时间内完成 查找。 (3)根据计算出的最优解的值构造对应的最优解。

3.1 矩阵链乘法 给定一个由n个矩阵构成矩阵序列(链)<A1, A2, ..., An>,要将它们相乘(假定它们按此序列是 乘法相容的：Ai是pi-1 pi矩阵，而Ai+1是pi pi+1矩 阵),计算积： A1A2 ... An 只要对此序列加上括号，确定运算顺序，就可以 算得它们的积。矩阵链的积称为是完全加括号的， 若它或是单一的矩阵，或是两个完全加括号的矩 阵子链之积，并用一对括号括起来。

1.问题的理解与描述 输入：数组<p0, p1, …, pn>,其中pi-1和pi分 别是矩阵Ai的行数和列数，i=1, 2, …, n。 输出：计算积A1A2 ... An的最优完全加括号 形式。

2.最优子结构 假定Ai Ai+1… Aj的最优完全加括号在Ak及 Ak+1之间分裂。则该加括号的“前缀”子 链Ai Ai+1… Ak在Ai Ai+1… A j的此最优加括号 中的完全加括号必为Ai Ai+1… Ak的最优加括 号。 设m[i, j]为计算矩阵所需的最少标量乘法次 数 ，根据上面的最优子结构的讨论，我们 i j 0 有：[i, j ] m i k j min{m[i, k ] m[k 1, j ] pi 1 pk p j } i j

3.子问题重叠性

4.算法的伪代码描述 MATRIX-CHAIN-ORDER(p) 1 n ← length[p] - 1 2 for i ← 1 to n 3 do m[i, i] ← 0 4 for l ← 2 to n l 是矩阵链的长度 5 do for i ← 1 to n - l + 1 6 do j ← i + l - 1 7 m[i, j] ← ∞ 8 for k ← i to j - 1 9 do q ← m[i, k] + m[k + 1, j] + pi-1 pkpj 10 if q < m[i, j] 11 then m[i, j] ← q 12 s[i, j] ← k 13 return m and s

5.算法的运行时间 算法有三重循环，每个循环变量

(l、i 及k) 最多取n-1个值，可得该算法的运行时间是 Θ(n3)。

6.构造一个最优解 利用MATRIX-CHAIN-ORDER(p)返回的数表s,可以 通过下列过程构造一个最优解。 PRINT-OPTIMAL-PARENS (s, i, j) 1 if i = j 2 then print "A"i 3 else print "(" 4 PRINT-OPTIMAL-PARENS (s, i, s[i, j]) 5 PRINT-OPTIMAL-PARENS (s, s[i, j] + 1, j) 6 print ")"

3.2 最长公共子序列 1.问题的理解与描述 最长公共子序列(LCS)问题形式化为： 输入：序列X = <x1, x2, ..., xm>和Y = <y1, y2, ..., yn>。 输出：X与Y的一个最长公共子序列Z。

2.最优子结构与子问题的重叠 定理3-1(最长公共子序列的最优子结构) 设X = <x1, x2, ..., xm>和Y = <y1, y2, ..., yn>为两个 序列，并设Z = <z1, z2, ..., zk>为X 和Y的任一LCS。 (1)若xm = yn,则zk = xm = yn且Zk-1是Xm-1和Yn1的一个LCS。 (2)若xm ≠ yn,则zk ≠ xm蕴含着Z是Xm-1和Y的 一个LCS。 (3)若xm ≠ yn,则zk ≠ yn蕴含着Z是X 和Yn-1的一 个LCS。

设c[i, j]为子序列Xi和Yj的LCS的长度。根据 最长公共子序列问题的最优子结构得出下 列递归式：i 0或j 0 0 c[i, j ] c[i 1, j 1] 1 i, j 0且xi y j max(c[i, j 1], c[i 1, j ]) i , j 0且x y i j c[2,2]

c[1,1]

c[1,2]

c[2,1] c[1,0] c[1,1] c[2,0]

c[0,0] c[1,0] c[0,1] c[0,1] c[0,2] c[1,1]

c[0,0] c[1,0] c[0,1] c[0,0] c[1,0] c[0,1]

3.算法的伪代码描述 LCS-LENGTH (X, Y) 1 m ← length[X] 2 n ← length[Y] 3 for i ← 1 to m 4 do c[i, 0] ← 0 5 for j ← 0 to n 6 do c[0, j] ← 0 7 for i ← 1 to m 8 do for j ← 1 to n 9 do if xi = yj 10 then c[i, j] ← c[i - 1, j - 1] + 1 11 else if c[i - 1, j] c[i, j - 1] 12 then c[i, j] ← c[i - 1, j] 13 else c[i, j] ← c[i, j - 1] 15 return c

4.构造一个最优解 PRINT-LCS(c, X, Y, i, j) 1 if i = 0 or j = 0 2 then return 3 if xi = yj 4 then PRINT-LCS (c, X, Y, i - 1, j - 1) 5 print xi 6 elseif c[i - 1, j] c[i, j - 1] 7 then PRINT-LCS (c, X, Y, i - 1, j) 8 else PRINT-LCS (c, X, Y, i, j - 1)

5.算法的运行时间 过程LCS-LENGTH的主体是第7~8行两重 嵌套的for循环，容易看出其时间复杂度为 T(m, n)= Θ(mn),其中m,n分别为X和Y的 长度。而过程PRINT-LCS的时间复杂度为 T(m, n)= Θ(m+n)。

3.3 0-1背包问题 1.问题的理解与描述 设有n种物品，第i种物品的重量为wi,价值为vi,i=1, 2, …, n。给定一个背包，最多能装重为C的物品。第i种物 品或放入包中，或留在包外。问将哪些物品放到包内能使 得包中所装物品总价值最大？其中，wi、vi都是正整数， i=1, 2, …, n。C也是正整数。如果我们用一个向量x=(x1, x2, …, xn)来表示此问题的解，其中 ，则0-1背包问题可

形 式化地描述为： 输入：集合W={w1, w2, …, wn},V={v1, v2, …, vn},数值C。 输出：向量x=(x1, x2, …, xn),xi {0,1},1 n,使得 i xiwi C,且 xivi最大。

2.最优子结构与子问题的重叠 定理3-2(0-1背包问题的最优子结构) 设y=(y1, y2, …, yi)是W={w1, w2, …, wi},V={v1, v2, …, vi}, 数值为j的0-1背包问题的一个最优解。 (1)若wi >j,则y'=( y1, y2, …, yi-1)为W={ w1, w2, …, wi-1}, V={ v1, v2, …, vi-1},数值j的子问题的最优解。 (2)若wi j,且yi =0,则y'=( y1, y2, …, yi-1)为W={ w1, w2, …, wi-1},V={ v1, v2, …, vi-1},数值j的子问题的最优解。 (3)若wi j,且yi =1,则y'=( y1, y2, …, yi-1)为子问题 W={ w1, w2, …, wi-1},V={ v1, v2, …, vi-1},数值j-wi的最优 解。

设m[i, j]是子问题W={w1, w2, …, wi }, V={v1, v2, …, vi },数值j 的最优解的目标值， 其中，i=1, 2, …, n,j=1, 2, …, C。根据最 优子结构特性，有i 0或j 0 0 m[i, j ] m[i 1, j ] i 0且wi j max{v m[i 1, j w ], m[i 1, j ]} i 0且w j i i i m[4,9] m[3,9] m[3,4]

m[1,5]

m[2,5] m[1,2] m[1,4]

m[2,4] m[1,1]

m[0,5]

m[0,3] m[0,2]

m[0,0]

m[0,4]

m[0,2]

m[0,1]

3.算法的伪代码描述 KNAPSACK(v, w, C) 1 n length[v] 2 for j 0 to C 3 do m[0, j] 0 4 for i 1 to n 5 do m[i, 0] 0 6 for j 1 to C 7 do m[i, j] m[i-1, j] 8 if wi ≤j 9 then if vi + m[i-1, j - wi] > m[i-1, j] 10 then m[i, j] vi + m[i-1, j - wi] 11 return m

本文来源：https://www.bwwdw.com/article/aube.html