第六章 动态规划方法
§1 动态规划算法的基本思想
动态规划方法是处理分段过程最优化 问题的一类及其有效的方法。 在
实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任
一阶段后的行为依赖于该阶段的状态， 而与该阶段之前的过程如何达
到这种状态的方式无关。这类问题的解 决是多阶段的决策过程。在
50 年代，贝尔曼（ Richard Bellman）等人提出了解决这类问题的“最
优化原理” ，从而创建了最优化问题的一种新的算法设计方法－动态
规划。
最优化原理： 多阶段过程的最优决策序列应当具有性质：无论过程的
初始状态和初始决策是什么， 其余的决策都必须相对于初始决策
所产生的状态构成一个最优决策序列。
对于一个多阶段过程问题， 上述最优决策是否存在依赖于该问题是否
有最优子结构性质： 原问题的最优解包含了其子问题的最优解。 而能
否采用动态规划的方法还要看该问题的子问题是否具有 重叠性质 。 后
面将会看到问题的 子结构性质 和 子问题重叠性质 是采用动态规划算
法的两个基本要素。先看两个例子：
例 1． 多段图问题
设 G=(V,E)是一个赋权有向图， 其顶点集 V 被划分成 k>2 个不相
交的子集 V
i
: 1≤i≤k，其中， V
1
和 V
k
分别只有一个顶点 s(称为源 )和一
个顶点 t(称为汇 )， 图中所有的边 (u,v)的始点和终点都在相邻的两个子
集 V
i
和 V
i
＋
1
中： u∈V
i
， v∈V
i
＋
1
。
V
1
V
2
V
3
V
4
V
5
4 6
9 4 4
2 5
7 2
S 7 3 2 t
3 1
11 5
2 5
11 6
8
一个 5 阶段的网络图
多阶段图问题： 求由 s 到 t 的最小成本路径 。
对于每一条由 s 到 t 的路径，可以把它看成在 k-2 个阶段作出的某个
决策序列的相应结果：第 i 步决策就是确定 V
i+1
中那个顶点在这条路
径上。今假设 s, v
2
, v
3
, … , v
k-1
, t 是一条由 s 到 t 的最短路径，再假定
从源点 s(初始状态 )开始，已经作出了到顶点 v
2
的决策 (初始决策 ),则
v
2
就是初始决策产生的状态。若将 v
2
看成是原问题的子问题的初始
状态，解这个子问题就是找一条由 v
2
到 t 的最短路径。事实上，这条
最短路径一定是 v
2
, v
3
, … , v
k-1
, t。不然，设 v
2
, q
3
, … , q
k-1
, t 是一条由
v
2
到 t 的比 v
2
, v
3
, … , v
k-1
, t 更短的路径，则 s, v
2
, q
3
, … , q
k-1
, t 是一条
由 s 到 t 的比 s, v
2
, v
3
, … , v
k-1
, t 更短的路径。与前面的假设矛盾。这
说明多段图问题具有最优子结构性质。
例 2． 经典 0/1 背包问题
有 n 件物品，第 i 件重量和价值分别是 w
i
和 p
i
, i=1, 2, …, n。要
将这 n 件物品的一部分装入容量为 c 的背包中， 要求每件物品或整个
1
2
4
6
9
10
11
12
3
7
8
5
装入或不装入，不许分割出一部分装入。 0/1 背包问题就是要给装包
算法，使得装入背包的物品的总价值最大。这个问题归结为数学规划
问题：
∑
≤≤ ni
ii
xp
1
max
s.t. nixcxw
i
ni
ii
,,2,1},1,0{,
1
L=∈≤
∑
≤≤
（ 6.1）
0/1 背包问题具有最优子结构性质。 事实上， 若
n
yyy ,,,
21
L是最优解，
则
n
yy ,,
2
L将是是 0/1 背包问题的子问题
∑
≤≤ ni
ii
xp
2
max
s.t. nixwcxw
i
ni
ii
,,2},1,0{,
1
2
L=∈?≤
∑
≤≤
(6.2)
最优解。因为，若
n
yy ',,'
2
L是子问题 (6.2)的最优解，且使得
∑
≤≤ ni
ii
yp
2
' >
∑
≤≤ ni
ii
yp
2
(6.3)
则
n
yyy ',,',
21
L将是原问题 (6.1)的可行解，并且使得
∑
≤≤
+
ni
ii
ypyp
2
11
' >
∑
≤≤ ni
ii
yp
1
(6.4)
这与
n
yyy ,,,
21
L是最优解相悖。
例 3． 矩阵连乘问题
给定 n 个数字矩阵 A
1
， A
2
， …， A
n
，其中 A
i
与 A
i+1
是可乘的，
i=1,2,…,n-1.求矩阵连乘 A
1
A
2
???A
n
的加括号方法，使得所用的数乘次
数最少。
考察两个矩阵相成的情形： C=AB.如果矩阵 A， B 分别是 p× r
和 r× q 矩阵，则它们的乘积 C 将是 p× q 矩阵，其 (i, j)元素为
∑
=
=
r
k
kjikij
bac
1
(6.5)
i=1,…,p, j=1,…,q, 因而 AB 所用的数乘次数是 prq。如果有至少 3 个
以上的矩阵连乘则涉及到乘积次序问题，即加括号方法。例如 3 个
矩阵连乘的加括号方法有两种： ((A
1
A
2
)A
3
)和 (A
1
(A
2
A
3
))。设 A
1
， A
2
，
A
3
分别是 p
0
× p
1
， p
1
× p
2
， p
2
× p
3
矩阵，则以上两种乘法次序所用的
数乘次数分别为： p
0
p
1
p
2
+p
0
p
2
p
3
和 p
0
p
1
p
3
+p
1
p
2
p
3
。如果 p
0
=10, p
1
=100,
p
2
=5, p
3
=50, 则两种乘法所用的数乘次数分别为： 7500 和 750000。可
见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。
对于 n 个矩阵的连乘积，令 P(n)记连乘积的完全加括号数，则有如下
递归关系
?
?
?
?
?
>?
=
=
∑
?
=
1
1
1)()(
11
)(
n
k
nknPkP
n
nP (6.6)
由此不难算出 P=C(n-1),其中 C 表示 Catalan 数：
)/4(
2
1
1
)(
2/3
n
n
n
n
nC
n
?=
?
?
?
?
?
?
+
= (6.7)
也就是说， P(n)是随 n 指数增长的，所以，我们不能希望列举所有可
能次序的连乘积， 从中找到具有最少数乘次数的连乘积算法。 事实上，
矩阵连乘积问题具有最优子结构性质，我们可 以采用动态规划的方
法，在多项式时间内找到最优的连乘积次序。
用 A[i:j]表示连乘积 A
i
A
i
＋
1
???A
j
.分析计算 A[1:n]的一个最优次序。
设这个计算次序在矩阵 A
k
和 A
k+1
之间将矩阵连分开， 1≤k<n，则完
全加括号方式为 ((A
1
A
2
???A
k
)( A
k
＋
1
???A
n
))，依此次序，我们先分别计算
A[1:k]和 A[k+1:n]，然后将计算的结果相乘得到 A[1:n]。可见， A[1:n]
的一个最优序所包含的矩阵计算子链 A[1:k]和 A[k+1:n]的次序也一定
是最优的。也就是说，矩阵连乘问题具有最优子结构性质。
如上三个例子都具有最优子结构性质， 这个性质决定了解决此类
问题的基本思路是： 首先确定原问题的最优值和其子问题的最优值之
间的递推关系，然后自底向上递归地构造出最优解。最优子结构性质
是最优化原理得以采用的先决条件。一般说来，分阶段选择策略确定
最优解的问题往往会形成一个决策序列。 Bellman 认为，利用最优化
原理以及所获得的递推关系式去求解最优决策序列， 可以使枚举数量
急剧下降。这里有一个问题值得注意：最优子结构性质提示我们使用
最优化原理产生的算法是递归算法， 这很可能会增加时间与空间复杂
度。例如，用递归式直接计算矩阵连乘积 A[1:n] 的算法
RecurMatrixChain 的时间复杂度将是 )2(
n
? ：
计算矩阵连乘的递归算法
int RecurMatrixChain(int i, int, j, int p)
{
if (i==j) return 0;
int u=RecurMatrixChain(i, i)
+RecurMatrixChain(i+1,j)
+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1; k<j; k++){
int t=RecurMatrixChain(i,k)
+RecurMatrixChain(k+1,j)
+p[i-1]*p[i]*p[j];
if (t<u) {
u=t;
s[i][j]=k;}
}
return u;
}
如果用 T(n)表示该算法的计算 A[1:n]的时间，则有如下递归关系式：
?
?
?
?
?
>+?++
=
≥
∑
?
=
1
1
1)1)()((1
1)1(
)(
n
k
nknTkT
nO
nT
当 1>n 时
∑∑∑
?
=
?
=
?
=
+=++?+≥
1
1
1
1
1
1
)(2)()()1(1)(
n
k
n
k
n
k
kTnknTkTnnT － ，
可用数学归纳法直接证明： )2(2)(
1 nn
nT ?=≥
?
，这显然不是我们所
期望的。
注意到，在用递归算法自顶向下求解具有最优子结构的问题时，
每次产生的子问题并不总是新问题，有些问题被反复计算多次。动态
规划算法正是利用了这种子问题的重叠 性质，对每一个问题只解一
次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简
单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题
的大小呈多项式增长。 因此， 用动态规划算法通常只需要多项式时间，
从而获得较高的效率。所以，可用动态规划算法求解得的问题应具备
的另一个基本要素是 子问题的重叠性 。 例如， 在矩阵的连乘积问题中，
若用 m[i][j]表示由第 i 个矩阵到第 j 个矩阵的连乘积所用的最少数乘
次数，则计算 m[1][n]时的子问题共有 )(
2
nΘ 个。这是因为，对于
nji ≤≤≤1 不同的有序对 (i, j)对应于不同的子问题， 不同子问题最多
只有 )(
2
2
nn
n
Θ=+
?
?
?
?
?
?
个。用动态规划解此问题时，在计算过程中，保
存已解决的子问题答案，每个子问题只计算一次，而在后面用到时简
单地查一下，从而避免了大量的重复计算。
求矩阵连乘最优次序的动态规划算法
void MatrixChain(int p, int n, int * *m, int * *s)
{
for (int i=1; i<=n; i++) m[i][i]=0;
for (int r=2; r<=n; r++){
for (int i=1; i<=n-r+1; i++)
int j=i+r-1;
m[i][j]= m[i+1][j]+p[i-1]*p[i]*p[j];
s[i][j]=i;
for (int k=i+1; k<j; k++){
int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j];
if (t< m[i][j]) {
m[i][j]=t;
s[i][j]=k; }
}
}
}
算法 MatrixChain 的主要计算量取决于程序中对 r, i 和 k 的三重循环，
循环体内的计算量为 O(1)，三重循环的总次数是 O(n
3
)，所以，算法
的计算时间上界为 O(n
3
)。
注意， 上述算法只是明确给出了矩阵最优连乘次序所用的数乘次
数 m[1][n]，并未明确给出最优连乘次序，即完全加括号方法。但是
以 s[i][j]为元素的 2 维数组却给出了足够的信息。事实上， s[i][j]=k
说明，计算连乘积 A[i:j]的最佳方式应该在矩阵 A
k
和 A
k+1
之间断开，
即最优加括号方式为 (A[i:k])(A[k+1:j])。下面的算法 Traceback 按算法
MatrixChain 计算出的断点信息 s 指示的加括号方式输出计算 A[i:j]的
最优次序。
根据最优值算法构造最优解
Void Traceback(int i, int j, int * * s)
{
if (i==j) return;
Traceback(i, s[i][j], s);
Traceback(s[i][j]+1, j, s);
cout << “Multiply A” << i << “,” << s[i][j];
cout << “and A” << (s[i][j] +1) << “,” << j; << endl;
}
总结上面解矩阵连乘积问题，我们 可以归纳出使用动态规划算法
的基本步骤：
1． 分析最优解的结构
在这一步中，应该确定要解决的问题 应该是具有最小子结构性质，
这是选择动态规划算法的基础。
2． 建立递归关系
第一步的结构分析已经为建立递归关系奠定了基础。 这一步的主要
任务是递归地定义最优值， 并建立该问题与其子问题最优值之间的
递归关系。例如在矩阵连乘积问题中，递归关系为
{}
?
?
?
<+++
=
=
≤≤
ji]]*p[k]*p[jp[i-] [j] m[km[i] [k]
ji
jim
jki
11min
0
]][[
在经典 0/1 规划问题中的递归关系是
{ }
1111
)(),(max)(
++++
+?=
jjjj
pwXgXgXg (6.8)
在多段图问题中的递归关系是
{ }),1(),(min),(
),(,
1
liCOSTljcjiCOST
EliVl
i
++=
∈∈
+
(6.9)
这里 j 表示取 V
i
中的顶点 j。
3． 计算最优值
依据递归关系式可以自底向上的方式或自顶向下的方式进行计算，
在计算过程中保存已经解决的子问题答案。每个子问题只计算一次，
而在后面需要时只要简单查一下，从而避免大量的重复计算，最终获
得多项式时间的算法。
4． 造最优解
依据求最优值时记录的信息，构造出最优解。
上述归纳的 4 个阶段是一个整体，必要时才分步完成，很多时是统
一来完成的。
§2 多段图问题
多段图是一种简单而经典的模型， 它既能地反映了动态规划算法的基
本特征，而且在实际问题中有较多的应用。
V
1
V
2
V
3
V
4
V
5
7 4
4 6
9 7 4 4
9 2 5
7 2
S 7 5 3 2 2 t
16 3 18 1
11 5
2 7 5
15 11 6 5
8
由后向前的处理方法（动态规划方法）
V
1
V
2
V
3
V
4
V
5
9 13
4 6
9 9 4 4
7 2 5
7 2
S 7 11 3 14 2 t
3 3 1 16
11 5
2 10 5
2 11 6 16
8
由前向后的处理方法（备忘录方法）
根据 (6.9)式，我们可以由后向前逐步确定各阶段中的顶点到汇顶点 t
的最短路径。对于如上的 5 阶段网络图，上图中的红色字体标出了各
顶点到汇顶点 t 的最短距离。
事实上，我们也可以由前向后逐步确定由源顶点 s 到各阶段中顶
1
2
4
6
9
10
11
12
3
7
8
5
1
2
4
6
9
10
11
12
3
7
8
5
点的最短路径，此时的递归关系为
{ }),(),1(min),(
),(,
1
jlcliCOSTjiBCOST
EjlVl
i
+?=
∈∈
?
(6.10)
多段图的动态规划算法伪代码
MultiGraph(E, k, n, P) //有 n 个顶点的 k 段图 G（按段序统一
//编号） ， E 是边集， c(I, j)是边 (I, j)的成本， P[1:k]是最小成
//本路径。
1 real COST(n); integer D(n-1)， P(k), r, j, k, n;
2 COST(n)=0;
3 for j from n-1 by –1 to 1 do
4 设 r 是这样一个顶点， (j, r)∈E 且使得 c(j, r)+COST(r)取最
小值
5 COST(j)= c(j, r)+COST(r);
6 D(j)=r;
7 endfor
8 P(1)=1; P(k)=n;
9 for j from 2 to k-1 do
10 P(j)=D(P(j-1));
11 endfor
12 end MultiGraph
这里， D(j)将由 j 到汇顶点 t 的最短路径上 j 后面的顶点记录下来， P(j)
则记录由源顶点 s 到汇顶点 t 的最短路径上处于第 j 阶段中的顶点。
语句 10 是根据数组 D 中的信息逐段寻找到由源顶点 s 到汇顶点 t 的
最短路径上的各个顶点。如果用邻接表表示图 G，则语句 4 中 r 的确
定可以在与 d
＋
(j)成正比的时间内内完成。因此，语句 3－ 7 的 for 循
环所需的时间是 |)|( En+Θ 。循环体 9－ 11 所需时间是 nk ≤Θ )( ，因
而算法 MultiGraph 的时间复杂度是 |)|( En+Θ 。 下面给出的备忘录算
法的时间复杂度也是若此。
多段图的备忘录算法伪代码
MemorizedMultiGraph(E, k, n, P) //有 n 个顶点的 k 段图 G（按
//段序统一编号） ， E 是边集， c(I, j)是边 (I, j)的成本， P[1:k]
//是最小成本路径。
1 real BCOST(n); integer D(n-1), P(k), r, j, k, n;
2 BCOST(1)=0;
3 for j from 2 to n do
4 设 r 是这样一个顶点， (r, j)∈E 且使得 BCOST(r)+ c(r, j)
取最小值
5 BCOST(j)= BCOST(r)+ c(r, j);
6 D(j)=r;
7 endfor
8 P(1)=1; P(k)=n;
9 for j from k-1 by –1 to 2 do
10 P(j)=D(P(j+1));
11 endfor
12 end MemorizedMultiGraph
§ 3 0/1 背包问题
本节将使用动态规划的由前向后处理方法（也称备忘录算法）处理
0/1 背包问题：
∑
≤≤ ni
ii
xp
1
max
s.t. nixcxw
i
ni
ii
,,2,1},1,0{,
1
L=∈≤
∑
≤≤
（ 6.1）
通过作出变量 x的取值序列
n
xxx ,,,
21
L来给出最优解。 这个取值序列
的对应的决策序列是
11
,,, xxx
nn
L
?
。在对
n
x 作出决策之后，问题
处于下列两种状态之一：背包剩余的容量仍为 c，此时未产生任何效
益；背包的剩余容量为
n
wc ? ，此时的效益值增长了
n
p 。因而
}]][1[],][1[max{]][[
nn
pwcnmcnmcnm +???= (6.11)
一般地，如果记
0/1 背包子问题问题：
∑
≤≤ ki
ii
xp
1
max
s.t. kixXxw
i
ki
ii
,,2,1},1,0{,
1
L=∈≤
∑
≤≤
(6.12)
最优解的值为 ]][[ Xkm ，则有
}]][1[],][1[max{]][[
kk
pwXkmXkmXkm +???= (6.13)
这里 cX ≤≤0 ，而 且 nk ,,2L= 。为 使 (6.13)式能够有效地递推下去，
需要延拓 k 和 X 的取值范围： ),(;,2,1 +∞?∞∈= XnkL；补充定义：
nkkm
Xif
Xif
XmL,2,1,]0][[
;00
;0
]][0[ =?∞=<
?
?
?
≥
<∞?
= (6.14)
事实上，我们主要目的是计算出 ]][[ cnm ，根据 (6.11)式，我们
可能需要计算 ]][1[
n
wcnm ?? ，而为了计算 ]][1[
n
wcnm ?? ，可能需
要计算 ]][2[
1 nn
wwcnm ???
?
，如此等等，在递推公式 (6.13)中用到
的 X 值可能为负数。另外，如果将 ]][[ Xkm 看作 X 的函数，则是一
个分段函数，而且当
∑
≤≤
≥
ki
i
wX
1
时取常值。所以将 X 的取值范围延拓
至全体实数。
例子 5),5,2,1(),,(),4,3,2(),,(,3
321321
==== cwwwwwwn 。
33
22
11
]][2[
98}53,2max{
977}52,3max{
766}51,3max{
655}50,3max{
545}50,2max{
432
321
200
0
]][2[
]][1[
53}21,1max{
532}20,1max{
321
200
0
]][2[
]][0[
21}10,0max{
200
0
]][1[
,
00
0
]][0[
pwXm
X
X
X
X
X
X
X
X
X
Xm
pwXm
X
X
X
X
X
Xm
pwXm
X
X
X
Xm
X
X
Xm
+?
?
?
?
?
?
?
?
?
?
?
?
?
?
≤=+
<≤=+
<≤=+
<≤=+
<≤=+
<≤
<≤
<≤
<∞?
=
+?
?
?
?
?
?
?
?
≥=+
<≤=+
<≤
<≤
<∞?
=
+?
?
?
?
?
?
≥=+
<≤
<∞?
=
?
?
?
≥
<∞?
=
由递推式 (6.13)， ]][[]][1[ XkmXkm ≤? ，而且当
k
wX < 时等式成立，这
一事实可以写成
nk
wXpwXkmXkm
wXXkm
Xkm
kkk
k
,,2,1
},]][1[],][1[max{
],][1[
]][[
L=
?
?
?
≥+???
<?
=
上述诸函数 ]][[ Xkm 具有如下性质：
1．每个阶梯函数 ]][[ Xkm 都是由其跳跃点偶 ])][[,( bkmb 决定的。如
果有 1+r 个跳跃点 :
r
bbb <<<L
10
，各点的函数值分别是
r
vvv ,,,
10
L，则
ribXbifvXkm
iii
,,1,0,]][[
1
L=<≤=
+
(6.15)
这里约定 +∞=
+1r
b 。
2．令 S
k
是阶梯函数 ]][[ Xkm 的跳跃点偶的集合，则阶梯函数
kk
pwXkm +?? ]][1[ 的跳跃点偶之集去掉点偶 (0,0)后，恰是集合
i
a
S ={ }
1
),(|),(
?
∈??
k
kk
Spvwbvb (6.16)
这是因为函数
kk
pwXkm +?? ]][1[ 的图象恰是由函数 ]][1[ Xkm ?
的图象先向右平移
k
w ，然后再向上移动
k
p 而得。如前面例子
m[1][X-w
2
]+p
2
3 3
2 m[1][X] 2
1 1
b b
0 1 2 3 4 5 6 0 1 2 3 4 5 6 7
S
1
={(0,0), (2,1)} (w
2
, p
2
)=(3, 2) S
2
a
={ (3,2), (5,3)}
m[2][X]
3
2
1 S
2
={(0,0), (2,1), (3,2), (5,3)}
0 1 2 3 4 5 6 7 b
根据递推公式 (6.13)， S
k
是从 S
k-1
∪ S
k
a
中去掉那些点偶 ),(
ii
vb ： 在 S
k-1
∪
S
k
a
中存在点偶 ),(
kk
vb 使得
ki
bb ≥ 而且
ki
vv ≤ ， 此时我们说 ),(
kk
vb 淹
没 ),(
ii
vb 。前面例子的诸 S
k
计算如下：
)}.8,9(),7,7(),6,6(),5,4(),2,3(),1,2(),0,0{(
)}8,9(),7,7(),6,6(),5,4{(),(
),5,4(),()};3,5(),2,3(),1,2(),0,0{(
)}3,5(),2,3{(),(),2,3(),()};1,2(),0,0{(
)}1,2{(),(),1,2(),()};0,0{(
3
2
33
3
33
2
1
22
2
22
1
0
11
1
11
0
=
=+=
==
=+===
=+===
S
SpwS
pwS
SpwSpwS
SpwSpwS
a
a
a
在由
2
S 、
3
a
S 向
3
S 的归并过程中， (5, 3)被 (4, 5)淹没。
3．在处理实际问题时，由于要求 cX ≤ ，在计算
1
),(
?
+=
k
kk
k
a
SpwS 时应该去掉那些使得 cb > 的跳跃点偶 ),( vb 。根
据前面的提到的淹没规则，如果将
k
S 中的元素按照第一个分量的递
增次序排列，则第二个分量也呈递增的次序，而且
n
S 的最后一个元
素，设为 ),( vb ，的 v值即是 0/1 背包问题 (6.1)的最优值 ]][[ cnm 。
4．最优解的获得可以通过检查诸
k
S 来确定。设 ),(
nn
kk
vb 是
n
S 的
最后一个元素。 若
1
),(
?
∈
n
kk
Svb
nn
， 则 0=
n
x . 因为此时函数 ]][[ Xnm
和函数 ]][1[ Xnm ? 的最大值一致，表明 0/1 背包问题 (6.1)与其子问题
∑
?≤≤ 11
max
ni
ii
xp
s.t. 1,,2,1},1,0{,
11
?=∈?≤
∑
?≤≤
nixwcxw
in
ni
ii
L (6.17)
有相同的最优值。若
1
),(
?
?
n
kk
Svb
nn
，则 1=
n
x 。因为，此时函数
]][[ Xnm 的最大值是函数 ]][1[ Xnm ? 的最大值加
n
p ，相应地， 0/1 背
包问题 (6.1)的最优值是其子问题 (6.17)的最优值加
n
p 。注意到此时跳
跃点偶一定具有形式
),(),(),(
11 ??
+=
nnnn
kknnkk
vbpwvb (6.18)
其中
1
),(
11
?
∈
??
n
kk
Svb
nn
。于是，我们可以依
2
),(
11
?
∈
??
n
kk
Svb
nn
与否而
决定
1?n
x 取 0 或 1。 如此等等， 我们可以逐一确定
11
,,, xxx
nn
L
?
的值。
在上述例子中，整理后的诸
k
S 为：
)}.6,6(),5,4(),2,3(),1,2(),0,0{(
)};3,5(),2,3(),1,2(),0,0{(
)};1,2(),0,0{(
)};0,0{(
3
2
1
0
=
=
=
=
S
S
S
S
(6, 6)是
3
S 的最后一个跳跃点偶，所以该 0/1 问题的最优值是 6。这个
点偶不在
2
S 中，因而 1
3
=x ; 又
2
)1,2()5,4()6,6( S∈=? ，据此判断
2
x 的取值。因为
1
)1,2( S∈ ，所以 0
2
=x ；最后由
0
)1,2( S? 知 1
1
=x ，
所以最优解为 )1,0,1( .
为实现上述算法，可以用两个一维数组 B 和 V 来存放所有的跳
跃点偶 (b, v)，跳跃点集
110
,,,
?n
SSSL互相邻接地存放，并指针 F(k)
来指示集合 S
k
，即 S
k
的第一个元素的位置（这里不存放 S
n
是由于我
们只需要它的最后一个元素， 而这个元素或者是 S
n-1
的最后一个元素，
此时 S
n-1
与 S
n
有相同的最后元素；或者具有形式 (6.18)，而且
1?n
k
v 是
满足 cwv
nk
n
≤+
?1
的最大值。所以，确定 S
n
的最后元素不必将 S
n
的
元素全部求出来。而且 确定最优解的其它变量
11
,, xx
n
L
?
时也不使用
数据 S
n
） 。用 F(n)指示 S
n-1
的最后一个元素的位置。因为产生 S
k
仅使
用信息 S
k-1
和 ),(
kk
pw ，所以不必存储
k
a
S 。根据以上分析，我们不难
给出动态规划解 0/1 背包问题的算法伪代码。
0/1背包问题动态规划算法伪代码
DKnapsack(w, p, c, n, m) //数组 w, p 中的元素分别代表各件物品的
//重量和价值， n 是物品个数， c 代表背包容量
real p(n), w(n), B(m), V(m), ww, pp, c;
integer F[0:n], l, h, i, j, p, next;
F[0]=1; B[0]=V[0]=0;
l=1; h=1; //S
0
的首和尾
F(1)=2; next=2; // B、 V 中的第一个空位
for i from 1 to n-1 do
k=1;
u=最大指标 r，使得 1 ≤ r ≤ h, 而且 B[r]+w
i
≤ c;
for j from 1 to u do
(ww, pp)=( B[r]+w
i
, V[r]+p
i
); //S
i
a
中的下一个元素
while k ≤ h && B[k] < ww do //从 S
i-1
中取来元素归并
B[next]=B[k]; V[next]=V[k];
Next=next+1; k=k+1;
endwhile
if k ≤ h && B[k]=ww then
pp=max(B[k], pp);
k=k+1;
endif
if pp > V[next-1] then
(B[next], V[next])=(ww, pp);
next=next+1;
endif
while k ≤ h && V[k] < V[next-1] do //清除
k=k+1;
endwhile
endfor
while k ≤ h do // 将 S
i-1
剩余的元素并入 S
i
(B[next], V[next])= (B[k], V[k]);
next=next+1; k=k+1;
endwhile
l=h+1; h=next-1; F(I+1)=next; //为 S
i+1
赋初值
endfor
traceparts // 逐一确定
11
,,, xxx
nn
L
?
end Dknapsack
算法 DKnapsack 的主要工作是产生诸 S
i
。在 i > 0 的情况下，每
个 S
i
由 S
i-1
和 S
i
a
归并而成，并且 |S
i
a
| ≤ |S
i-1
|。因此 |S
i
| ≤ 2|S
i-1
|，
122||
1111
?==
∑∑
?≤≤?≤≤
n
ni
i
ni
i
S
由此知，算法 DKnapsack 的空间复杂度是 )2(
n
O 。
由 S
i-1
生成 S
i
需要 |)(|
1?
Θ
i
S 的时间， 因此， 计算
110
,,,
?n
SSSL总
共需要的时间为 122||
1
11
1
11
1
?=≤
?
?≤≤
?
?≤≤
?
∑∑
n
ni
i
ni
i
S ，算法 DKnapsack 的
时间复杂度为 )2(
n
O 。
如果物品的重量
i
w 和所产生的效益值
i
p 都是整数，那么，
i
S 中
的元素 ),( vb 的分量 b 和 v 也都是整数，且
∑
≤≤
≤≤
ik
k
pvcb
1
, 。又
i
S 中
不同的元素对应的分量也都是不同的，故
?
?
?
?
?
?
+≤
+≤
∑
∑
≤≤
≤≤
cwS
pS
ik
k
i
ik
k
i
,min1||
1||
1
1
此时算法 DKnapsack 的时间复杂度为 ),,2(min
1 ?
?
?
?
?
?
∑
=
n
i
k
n
pnncO 。
§4 流水作业调度问题
问题描述 ：已知 n 个作业 {1, 2, . . . , n}要在由两台机器 M
1
和 M
2
组成
的流水线上完成加工。每个作业加工的顺序都是先在 M
1
上加工，然
后在 M
2
上加工。 M
1
和 M
2
加工作业 i 所需的时间分别为 a
i
和 b
i
， 1≤ i
≤ n。流水作业调度问题要求确定这 n 个作业的最优加工次序，使得
从第一个作业在机器 M
1
上开始加工，到最后一个作业在机器 M
2
上
加工完成所需的时间最少。
记 N={1, 2, . . . , n}， S 为 N 的子集合。一般情况下，当机器 M
1
开始加工 S 中的作业时，机器 M
2
可能正在加工其它的作业，要等待
时间 t 后才可用来加工 S 中的作业。将这种情况下流水线完成 S 中的
作业所需的最短时间记为 T(S, t)，则流水作业调度问题的最优值即是
T(N, 0)。
流水作业调度问题具有最优子结构性质 。事实上，设 π 是 n 个流
水作业的一个最优调度（实际上是作业的一个排序） ，其所需要的加
工时间为 '
)1(
Ta +
π
，其中， 'T 是在机器 M
2
的等待时间为
)1(π
b 时，安
排作业 )(,),2( nππL所需的时间。若记 )}1({\ πNS = ，我们证明
),('
)1(π
bSTT = 。
首先由 'T 的定义知 ),('
)1(π
bSTT ≥ 。如果 ),('
)1(π
bSTT > ，设 'π 是
作业集 S 在机器 M
2
等等时间为
)1(π
b 情况下的一个最优调度，则
)(',),2('),1( nπππL是 N 的一个调度，该调度所需的时间为
'),(
)1()1()1(
TabSTa +<+
πππ
，这与 π 是 N 一个最优调度矛盾。所以
),('
)1(π
bSTT = ，说明流水作业调度问题具有最优子结构性质。
关于流水作业调度问题的最优值递推关系式， 我们可以如下建立。
容易看出
)}},{\({min)0,(
1
ii
ni
biNTaNT +=
≤≤
(6.19)
上述关系式可以推广到一般情形：
})}0,max{},{\({min),(
iii
Si
atbiSTatST ?++=
∈
(6.20)
其中， }0,max{
i
at ? 一项是由于在机器 M
2
上， 作业 i 必须在 },max{
i
at
时间之后才能开工。因此，在机器 M
1
完成作业 i 之后，机器 M
2
还需
等待
}0,max{},max{
iiiii
atbaatb ?+=?+
时间后才能完成对作业 i 的加工。
按照递归关系 (6.20)，我们容易给出流水调度问题的动态规划算
法， 但是其时间复杂度将是 )2(
n
O 。 以下我们将根据这一问题的特点，
采用 Johnson 法则简化算法，使得到时间复杂度为 )log( nnO 。
设 π 是作业集 S 在机器 M
2
的等待时间为 t 时的任一最优调度。若
在这个调度中，安排在最前面的两个作业分别是 ji和 ，即
ji == )2(,)1( ππ 。则由递归关系式 (6.20)的
)},,{\(})0,max{},{\(),(
ijjiiii
tjiSTaaatbiSTatST ++=?++=
其中
},,max{
}0,,max{
}},0,max{max{
}0,}0,max{max{
iijiijij
ijijij
ijijij
jiijij
abaataabb
baatabb
baatabb
aatbbt
?++??+=
??+?+=
??+?+=
??++=
如果作业 ji和 满足
},min{},min{
ijji
baba ≤ (6.21)
则称作业 ji和 满足 Johnson 不等式；如果作业 ji和 不满足 Johnson 不
等式，则交换作业 ji和 的加工次序使满足 Johnson 不等式。在作业集
S 当机器 M
2
的等待时间为 t 时的调度 π 中， 交换作业 ji和 的加工次序，
得到作业集 S 的另一个调度 'π ，它所需的加工时间为
)},,{\(),('
jiji
tjiSTaatST ++=
其中， },,max{
jjjiijijij
abaataabbt ?++??+= 。当作业 ji和 满
足 Johnson 不等式时 (6.21)时，有
},max{},max{
ijji
baba ??≥??
从而
},max{},max{
ijjijiji
baaabaaa ??++≥??++
由此可得 },max{},max{
iijijjji
abaaabaa ?+≥?+ 。因此，对于任
意 t 有 },,max{},,max{
iijijjji
abaatabaat ?+≥?+ ，即
ijji
tt ≥ 。
可见 ),(),(' tSTtST ≥ 。换句话说，当作业 ji和 不满足 Johnson 不等式
时，交换它们的加工次序后，作业 ji和 将满足 Johnson 不等式，而且
不会增加加工时间。由此可知，对于流水作业调度问题，必然存在一
个最优调度 π ，使得作业 )1()( +ii ππ 和 满足 Johnson 不等式：
11},,min{},min{
)()1()1()(
?≤≤≤
++
nibaba
iiii ππππ
一般地，可以证明，上述不等式与不等式
njibaba
ijji
≤<≤≤ 1},,min{},min{
)()()()( ππππ
(6.22)
等价。
以下给出的是流水作业调度问题的 Johnson 算法：
(1) 令 }|{},|{
iiii
abiBAbaiAB ≤=<= ;
(2) 将 AB中作业依
i
a 的非减次序排列；将 BA中作业依
i
b 的非增
次序排列；
(3) AB中作业接 BA中作业即构成满足 Johnson 法则的最优调
度。
流水作业调度问题的 Johnson 算法
int FlowShop(int n, int a, int b, int c)
{
class Jobtype{
public:
int operator <= (Jobtype a) const
{return (key <= a.key);}
int key;
int index;
bool job;
};
Jobtype *d=new Jobtype [n];
for (int i = 0; i< n; i++) {
D[i].key = a[i] > b[i] ? b[i] : a[i];
D[i].job = a[i] <= b[i];
D[i].index = i;
}
sort(d, n)
int j = 0, k = n-1;
for (int i = 0; i < n; i++) {
if ( d[i].job ) c[j++] = d[i].index;
else c[k--] = d[i].index;
}
j = a[c[0]];
k = j + b[c[0]];
for (int i = 1; i < n; i++) {
j + =a[c[i]];
k = j < k ? k + b[c[i]] : j + b[c[i]];
}
delete d;
return k;
}
上述算法的时间主要花在排序上，因此，在最坏情况下的时间复
杂度为 )log( nnO ，空间复杂度为 )(nO 更容易看出。
§5 最优二叉搜索树
设 },,,{
21 n
xxxSL= 是一个有序集合， 且
n
xxx <<<L
21
.表示有序
集合的二叉 搜索树利用二叉树的顶点存储有序集中的元素，而且具
有性质： 存储于每个顶点中的元素 x 大于其左子树中任一个顶点中存
储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶
点是形如 ),(
1+ii
xx 的开区间。在二叉搜索树中搜索一个元素 x，返回
的结果或是在二叉树的内部顶点处找到：
i
xx = ; 或是在二叉树的叶
顶点中确定： ),(
1+
∈
ii
xxx .现在假定在第一种情况出现，即
i
xx = 的
概率为
i
b ；在第二种情况出现，即 ),(
1+
∈
ii
xxx 的概率为
i
a .这里约定
+∞=?∞=
+10
,
n
xx . 显然
1;1,0;0,0
10
=+≤≤≥≤≤≥
∑∑
==
n
j
j
n
i
iji
banjbnia (6.23)
称集合 },,,,,{
110 nn
ababaL为有序集 S 的存取概率分布。
在一个表示 S 的二叉搜索树 T 种， 设存储元素
i
x 的顶点深度 （从
根到该顶点的距离）为
i
c ，叶顶点 ),(
1+ii
xx 的深度为
i
d ，则
∑∑
==
++=
n
j
jj
n
i
ii
dacbp
01
)1( (6.24)
表示在二叉搜索树 T 中做一次搜索所需的平均比较次数。 p也称为二
叉搜索树 T 的平均路长。
最优二叉搜索树问题对于有序集 S 及其存取概率分布
},,,,,{
110 nn
ababaL，在所有表示 S 的二叉搜索树中，找出一棵具有
最小平均路长的二叉搜索树。
为了采用动态规划算法， 我们首先要考虑该问题是否具有最优子
结构性质。二叉搜索树 T 的一棵含有顶点
jii
xxx ,,,
1
L
+
和叶顶点
),(,),,(),,(
111 ++? jjiiii
xxxxxxL的子树 T 可以看作是有序集
},,,{
1 jii
xxxL
+
关于全集为实数区间 ),(
11 +? ji
xx 的一棵二叉搜索树
（ T 自身可以看作是有序集 },,,{
21 n
xxxSL= 关于全集为整个实数
区间 ),( +∞?∞ 的子树） 。根据 S 的存取分布概率， x 在子树 T 的顶点
处被搜索到的概率是
∑∑
≤≤≤≤?
+=
jki
k
jki
kij
baw
1
(6.25)
于是 },,,{
1 jii
xxxL
+
的存储概率分布为 },,,,{
1 jjii
abbaL
?
，其中，
kh
ba , 分别是下面的条件概率：
jhiwaajkiwbb
ijhhijkk
≤≤?=≤≤= 1,;, (6.26)
设
ij
T 是有序集 },,,{
1 jii
xxxL
+
关于存储概率分布 },,,,{
1 jjii
abbaL
?
的一棵最优二叉搜索树，其平均路长记为
ij
p .
ij
T 的根顶点存储的元
素是
m
x ,其左子树
l
T 和右子树
r
T 的平均路长分别记为
l
p 和
r
p .由于
l
T
和
r
T 中顶点深度是它们在
ij
T 中的深度减 1，我们得
rjmlmiijijij
pwpwwpw
,11, +?
++= (6.27)
由于
l
T 是有序集 },,{
1?mi
xxL的一棵二叉搜索树，故
1, ?
≥
mil
pp .若
1, ?
>
mil
pp ， 则
1, ?mi
T 替换
l
T 可得到平均路长比
ij
T 更小的二叉搜索树。
这与
ij
T 是最优二叉搜索树矛盾。同理可证，
r
T 也是一棵最优二叉搜
索树。因此，最优二叉搜索树问题具有最优子结构性质。
x
6
T
l
T
r
T
2,10
采用上面的记号，则 n 元最优二叉搜索树问题即是求 T
1
，
n
，其最
优值为 p
1,n
。由最优儿茶搜索树的最优子结构性质，可以建立最优值
p
i,j
的递推公式：
jipwpwwpw
jkjkkiki
jki
ijijij
≤++=
++??
≤≤
},{min
,1,11,1,
(6.28)
初始时， nip
ii
≤≤=
?
1,0
1,
. 记
ijij
pw 为 ),( jim ，则
nnn
ppwnm
,1,1,1
),1( == 为所求最优值。由 (6.28)不难推得关于 ),( jim
的递推公式
niiim
jijkmkimwjim
jki
ij
,,2,1,0)1,(
)},,1()1,({min),(
L==?
≤++?+=
≤≤
(6.29)
据此，可以设计求解最优二叉搜索树问题的动态规划算法。
最优二叉搜索树的动态规划算法
void OptimalBinarySearchTree( int a, int b, int n,
int **m, int **s, int **w)
{
for (int i = 0; i < n; i++) {
w[i+1][i] = a[i];
x
4
x
3
x
5-
x
2
D
1
D
2
D
3
D
4
D
5
x
8
x
9
x
7
x
10
D
10
D
8
D
7
D
6
D
9
m[i+1][i] = 0;
}
for (int r = 0; ir< n; r++) {
for (int i = 1; i <= n-r; i++) {
int j = i+r;
w[i][j] = w[i][j-1] + a[j] +b[j];
m[i][j] = m[i+1][j];
s[i][j] = i;
for (int k =i + 1; k<= j; k++) {
int t = m[i][k-1] + m[k+1][j];
if (t < m[i][j]) {
m[i][j] = t;
s[i][j] = k; }
}
m[i][j]+=w[i][j];
}
}
}
算法 OptimalBinarySearchTree 中用 s[I][j]保存最优子树的根顶
点中元素。当 s[1][n] = k 时， x
k
为所求二叉搜索树的根顶点元素。其
左子树为 T(1,k-1)，因此 I = s[1][k-1]即表示 T(1,k-1)的根顶点为 x
i
。
依次类推， 容易由 s 记录的信息在 O(n)时间内构造出所求的最优二叉
搜索树。算法中用到三个数组 m、 s、 w，故所需的空间为 O(n
2
).算法
的主要计算量在于计算 )},1()1,({min jkmkimw
jki
ij
++?+
≤≤
。 对于固定
的差 r=j-I，需要计算时间 )1()1( +=+? rOijO 。因此算法所耗费的
总时间为
∑∑
?
=
?
=
=+
1
01
3
)()1(
n
r
rn
i
nOrO .
