第2部分 算法设计策略 第7章 动态规划法

7.1 一般方法和基本要素 7.2 每对结点间的最短路径 7.3 矩阵连乘 7.4 最长公共子序列 7.5 最优二叉搜索树 7.6 0/1背包 7.7 流水作业调度

7.1 一般方法和基本要素

7.1.3  多段图问题 例7－1 多段图G=(V,E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包含汇点（sink）t。对所有边<u,v>E，多段图要求若uVi，则vVi＋1，1i<k，每条边的权值为c(u,v)。从s到t的路径长度是这条路径上边的权值之和，多段图问题（multistage graph problem）是求从s到t的一条长度最短的路径。

子集Vi

多段图问题的特性 最优子结构特性 重叠子问题特性 （s,v2,v3,…,vk-1,t) 与 (v2,v3,…,vk-1,t) 定义cost(i,j)， 1i<k cost(k,t)=0 cost(i,j) = min { c(j,p) + cost(i+1,p) } 重叠子问题特性 第i阶段j状态的最短路径

1 — k段图的自后向前递推求解 递推关系式 cost(5,t)=0 cost(4,8)=?，cost(4,9)，cost(4,10)

【程序7－1】k段图的（从后）向前递推算法 template<class T> void Graph<T>::FMultiGraph(int k,int *p) {//采用程序6－8的邻接表存储图G。对图按阶段顺序标号 float *cost=new float[n]; //各节点的最短路径值 int q; int *d=new int[n]; //各结点开始的最短路径上的下一结点 cost[n-1]=0,d[n-1]=-1; //设置初值

for (int j=n-2;j>=0;j--){ float min=INFTY; for (ENode<T> *r=a[j];r;r=r->nextArc) { int v=r->adjVex; if (r->w+cost[v]<min) { min=r->w+cost[v]; q=v; } cost[j]=min;d[j]=q; p[0]=0; p[k-1]=n-1; //p记录最短路径 for(j=1;j<=k-2;j++) p[j]=d[p[j-1]]; delete []cost; delete []d;

2 — k段图的自前向后递推求解 递推关系式 cost(1,s)=0 cost(i,j)=?

动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。 分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。 贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。 动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。

7.1.1 一般方法 最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策对相应的子问题来说，必定构成最优策略。这便是最优决策序列的最优子结构特性。

基本要素 一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。

设计一个动态规划算法，通常可以按以下几个步骤进行： （1）刻画解的最优子结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。

7.1.4 资源分配问题 【例7－2】 将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。 （这里假设，对同一个项目，获得的资源越多，收益越多；不同的项目对资源的单位收益不一样）

4个资源、3个项目 V(i,j)表示j个资源已经分配给前i-1个项目 N(m,n)表示n个资源分配给第m个项目了

7.1.4 资源分配问题 向后递推的动态规划算法？

7.1.5 关键路径问题（略） 工程安排 最短工期 关键路径 关键活动 注意结点的编号 结点=事件（代表前一个活动结束， 后一个活动可开始的状态） 工程安排 最短工期 关键路径 关键活动 在关键路径上的活动 注意结点的编号

7.1.5 关键路径问题 最优子结构特性？ 子问题重叠？

7.2 每对结点间的最短路径

单源最短路径问题 单源最短路径问题是：给定带权的有向图G=(V,E)和图中结点sV，求从s到其余各结点的最短路径，其中，s称为源点。

贪心法求解 迪杰斯特拉（Dijkstra） 算法 已求得最短路径的结点集合记为S；源点s经过S中的结点到达结点v的所有路径中最短的一条称为v的特殊路径 开始时，S={s} 求其他不在S中结点的特殊路径 找出最短的特殊路径，将路径尾结点v加入S中 更新不在S中的结点的特殊路径，重复上一步直到G中所有结点都加入到S中。 {L1，L2，…，Ln-1}

6.6.3 迪杰斯特拉算法 【程序6－10】迪杰斯特拉算法 template<class T> class MGraph { 6.6.3 迪杰斯特拉算法 【程序6－10】迪杰斯特拉算法 template<class T> class MGraph { public: MGraph(int mSize); void Dijkstra(int s, T*& d, int*& path); ……

private: int Choose(int* d, bool* s); …… T** a; //邻接矩阵 int n; };

template <class T> int MGraph<T>::Choose(int* d, bool* s) { //找出在下一条当前最短路径上的尾结点 int i, minpos; T min; min=INFTY; minpos=-1; for (i=1;i<n;i++) if (d[i]<min &&!s[i]){ min=d[i]; minpos=i; } return minpos;

template <class T> void MGraph<T>::Dijkstra(int s, T*& d,int*& path) { int k,i,j; if (s<0||s>n-1) throw OutOfBounds; bool *inS=new bool[n]; //是否属于集合S d=new T[n]; path=new int[n]; for (i=0;i<n;i++){ //初始化d,inS,path inS[i]=false; d[i]=a[s][i]; if (i!=s && d[i]<INFTY) path[i]=s; else path[i]=-1; } 源点 最短路径上下一结点 最短路径长度

时间复杂度？ inS[s]=true; d[s]=0; for (i=1;i<n-1;i++){ //需要n-1步完成 k=Choose(d,inS); inS[k]=true; for (j=0; j<n; j++) //更新各结点的d和path if (!inS[j] && d[k]+a[k][j]< d[j]){ d[j]=d[k]+a[k][j]; path[j]=k; } 时间复杂度？

7.2.1 结点对间最短路径问题描述 设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数， 7.2.1   结点对间最短路径问题描述 设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数， 每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。

定义dk[i][j]=i到j的路径上，包含的结点编号 7.2.2 动态规划法求解 最优子结构 设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，(i,k) 和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)= (i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。 定义dk[i][j]=i到j的路径上，包含的结点编号 不超过k的最短路径长度

重叠子问题：为了计算dk[i][j]时，必须先计算 最优解的递推关系 重叠子问题：为了计算dk[i][j]时，必须先计算 dk－1[i][j]、dk－1[i][k]和dk－1[i][k]，dk1的元素被多个dk的元素的计算共享。 dk[i][j]指在i和j之间由编号不大于k的结点组成的最短路径长度。k=-1时表示不包含其他结点

7.2.3 弗洛伊德算法 弗洛伊德算法的基本思想是：令k=0,1,,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，d[i][j]存放从结点i到结点j的最短路径的长度。 在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。

【程序7－2】弗洛伊德算法 template<class T> void MGraph<T>::Floyd(T**& d, int **& path) { int i,j,k; d= new T*[n]; path=new int *[n]; for(i=0;i<n;i++){ //初始化 d[i]=new T [n]; path[i]=new int[n]; for (j=0; j<n; j++){ d[i][j]=a[i][j]; //邻接矩阵 if (i!=j && d[i][j]<INFTY) path[i][j]=i; else path[i][j]=-1; }

for (k=0;k<n;k++) //总共n步完成 for (i=0;i<n;i++) for (j=0;j<n;j++) if (d[i][k]+d[k][j] < d[i][j] ){ d[i][j]=d[i][k]+d[k][j]; path[i][j]=path[k][j]; } 弗洛伊德算法的时间复杂度为O(n3)

7.2.4 算法正确性 定理7－1 弗洛伊德算法得到的d[i][j]，0i,jn-1是从i到j的最短路径。

结点对间最短路径问题 弗洛伊德算法 N次迪杰斯特拉算法

7.3 矩阵连乘

7.3.1  问题描述 给定n个矩阵{A0,A1,…,An－1}， 其中Ai，i=0,…,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1…An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。 (((A0×A1) ×A3)×A4) (A0×((A1 ×A3)×A4))

例7－4 4个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040, C:4030, D:305。

× B C A=(M0×M1×M3×…×Mk) 完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。 A=M0×M1×M3×M4…Mn-1 A=(M0×M1×M3×…×Mk) × (Mk+1×Mk+2×…×Mn-1) B C

7.3.2 动态规划法求解 最优子结构 矩阵连乘AiAi+1…Aj简记为A[i:j]，ij。于是矩阵连乘A0A1…An-1可记作A{0:n-1}。将这一计算次序在矩阵Ak和Ak+1，0k<n-1之间断开，则其相应的完全加括号形式为（（A0A1…Ak）（Ak+1Ak+2…An1））。可先分别计算A[0:k]和A[k+1:n-1]，然后将两个连乘积再相乘得到A[0:n-1]。

矩阵连乘A[0:n-1]的最优计算次序的计算量等于A[0:k]和A[k+1:n-1]两者的最优计算次序的计算量之和，再加上A[0:k]和A[k+1:n-1]相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。

注意：N个矩阵的维数依序放在一维数组p中， 最优解的递推关系 先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。 注意：N个矩阵的维数依序放在一维数组p中， 其中Ai的维数记为Pi×Pi+1

求解过程 为避免重复计算，自底向上求解 m[i][j] m[i][k], k=i,i+1,…j-1 m[k+1][j], k=i+1,…j-1

7.3.3 矩阵连乘算法 【程序7－3】矩阵连乘算法 class MatrixChain { public: 7.3.3 矩阵连乘算法 【程序7－3】矩阵连乘算法 class MatrixChain { public: MatrixChain(int mSize,int *p); int MChain(); // 基于动态规划法 int LookupChain(); //基于备忘录的分治法 void Traceback(); //输出最优解 ……

private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,**m,**s, n; }; int MatrixChain::MChain() { //求A[0:n-1]的最优解值 for (int i=0;i<n;i++) m[i][i]=0; //主对角线

for (int r=2; r<=n;r++) //和主对角线平行的其他次对角线 for (int i=0;i<=n-r;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;k<j;k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]; if (t<m[i][j]) { m[i][j]=t; s[i][j]=k; } return m[0][n-1];

void MatrixChain::Traceback(int i,int j) { if(i==j) { cout<<'A'<<i;return;} if (i<s[i][j]) cout<<‘(’; //ai,ai+1,…,ak加括号 Traceback(i,s[i][j]); if (i<s[i][j]) cout<<')'; if(s[i][j]+1<j) cout<<'('; //ak+1,ak+2,…,aj加括号 Traceback(s[i][j]+1,j); if(s[i][j]+1<j) cout<<')'; } void MatrixChain::Traceback() cout<<'('; Traceback(0,n-1); cout<<')'; cout<<endl;

例7－5 6个矩阵连乘积A0A1A2A3A4A5，设它们的维数分别为A:3035，B:3515 C:155 D:510，E:1020，F:2025。

7.3.4  备忘录方法 矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而避免了相同子问题的重复求解。

【程序7－4】矩阵连乘的备忘录方法 int MatrixChain::LookupChain(int i, int j) { if (m[i][j]>0) return m[i][j]; //子问题已解。 if(i==j) return 0; int u=LookupChain(i+1,j)+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;k<j; k++) { int t=LookupChain(i,k)+LookupChain(k+1,j) +p[i]*p[k+1]*p[j+1]; if (t<u) { u=t; s[i][j]=k; } m[i][j]=u; return u;

int MatrixChain::LookupChain() { return LookupChain(0,n-1); }  

7.5 最优二叉搜索树

7.5.1 问题描述 设有元素集合{ a1,a2,…,an}，其中，a1<a2<…<an，p(i) 是在集合中成功查找ai 的概率，1i n，q(i)是待查元素x值满足 ai<x<ai+1的概率,0i n（假定a0= , an+1=+）。 最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。

二叉搜索树的代价 二叉搜索树平均搜索时间 {a1,…,an, E0,…,En} cost(T)= 内节点 外节点

=cost(L)+cost(R)+w(0,n) 递推关系 cost(T)= cost(L)+cost(R)+p1+…+pn +q0+q1+…+qn T =cost(L)+cost(R)+w(0,n) L R

7.5.2 动态规划法求解 设 c(0,n) 是由元素值集合{a1,…,an}所构造的最优二叉搜索树的代价，则 {a1,…,ak-1} 7.5.2 动态规划法求解 设 c(0,n) 是由元素值集合{a1,…,an}所构造的最优二叉搜索树的代价，则 {a1,…,ak-1} {ak} {ak+1,…,an}

一般地，c(i,j) ,ij 是元素值集合{ai+1,…,aj}所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足

例7－7 设n＝4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)＝(2,3,1,1,1)。这里p和q都已乘了16。

7.5.3 最优二叉搜索树算法 【程序7－7】构造最优二叉搜索树 int Find(int i, int j, int **r, float**c) //找出i,j之间使代价最小的根 { float min=INFTY; int k; for (int m=i+1;m<=j;m++) if ((c[i][m-1]+c[m][j])<min) { min=c[i][m-1]+c[m][j] ;k=m; } return k;

void CreateOBST(float* p, float* q, float **c, int **r, float**w,int n) { //初始化，主对角线，次主对角线 for (int i=0;i<=n-1;i++) { w[i][i]=q[i];c[i][i]=0.0;r[i][i]=0; w[i][i+1]=q[i]+q[i+1]+p[i+1]; c[i][i+1]=q[i]+q[i+1]+p[i+1]; r[i][i+1]=i+1; } w[n][n]=q[n];c[n][n]=0.0;r[n][n]=0;

算法复杂度 for (int m=2;m<=n;m++) for (i=0;i<=n-m;i++) { int j=i+m; w[i][j]=w[i][j-1]+p[j]+q[j]; int k = Find(i,j,r,c); c[i][j] = w[i][j] + c[i][k-1] + c[k][j]; r[i][j] = k; } 算法复杂度

7.6 0/1背包

7.6.1  问题描述 问题 已知一个载重为M的背包和n件物品，物品编号从0到n-1。第i件物品的重量为 wi，如果将第i种物品装入背包将获益pi，这里，wi>0，pi>0，0i<n。所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。

7.6.2  动态规划法求解 最优子结构 0/1背包的最优解具有最优子结构特性。设 (x0, x1,… , xn－1)，xi{0,1}是0/1背包的最优解，那么，(x1 ,x2,… , xn－1) 必然是以下0/1背包子问题的最优解： 背包载重Mw0x0，共有n-1件物品，第i件物品的重量为 wi，效益pi，wi>0，pi>0，1i<n。

递推关系分析 考虑这样的决策序列 设f(j,X)是当背包载重为X，可供选择的物品为0,1,2,…,j时的最优解值 xn-1,xn-2,…,x2,x0 设f(j,X)是当背包载重为X，可供选择的物品为0,1,2,…,j时的最优解值 f(n-1,M) = xn-1=0? f(n-2,M) xn-1=1? f(n-2,M-wn-1 )+pn-1

设有0/1背包问题n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和M=6。 例7－8 设有0/1背包问题n=3，（w0,w1,w2）=（2,3,4），（p0,p1,p2）=（1,2,4）和M=6。 x2=0 x2=1 +p2 +p1 +p0 x1=0 x1=1 x1=0 x0=0 x0=1 一般递归式

算法设计 递归算法 当物品重量、背包载重为整数时的动态规划算法 float f(int j, float X) 物品重量、背包载重可以为实数 时间复杂度为O(2n) 当物品重量、背包载重为整数时的动态规划算法 二维数组f[j][k] , j=0,1,…,n-1; k=0,1,2,…,M 设计从下向上的求解过程 时间复杂度O(nM)

如果X，wi为实数，f(j,X)为连续函数 f(-1,x-w0)+p0

现用Sj表示函数曲线f(j,X)的全部阶跃点的集合，Sj={(Xi,Pi)| 函数曲线f(j,X)的全部阶跃点}，-1jn-1，其中S-1={(0,0)}。用S1j表示函数曲线f(j-1,X-wj)+pj的全部阶跃点的集合，S1j={(Xj,Pj)| 函数曲线f(j-1,X-wj)+pj的全部阶跃点}，0j<n-1。

计算所有Sj和S1j的步骤如下： S-1={(0,0)}，函数f(-1,X)只有一个阶跃点； S1j={(X,P)|(X-wj,P-pj)Sj1，也就是说，由集合Sj-1中的每个阶跃点（X,P），得到集合S1j中的一个阶跃点（X+wj,P+pj）； Sj是合并集合Sj-1S1j，舍弃其中被支配的阶跃点和所有X>M的阶跃点得到。

对于例7－8有 S－1={(0,0)}，S10={(2,1) }} S0={(0,0),(2,1)}，S11={(3,2),(5,3)} S1={(0,0),(2,1),(3,2),(5,3)}， S12={(4,4),(6,5)，(7,6),(9,7)} S2={(0,0),(2,1),(3,2),(4,4),(6,5)}

【程序7－9】0/1背包算法的粗略描述 void DKP(float *p,float *w,int n, float M, float &P,int *x) { S－1={(0,0)}; for (i=0;i<n-1;i++){ S1i={(X,P)|(X-wi,P-pi)Si-1 and XM}; Si=MergerPurge(Si-1,S1i); }

(X1,P1)=Sn－2中最后一个阶跃点; (X2,P2)=(X+wn－1,P+pn－1)，其中(X,P)是Sn-1 中 使得 X+wn－1M的最大的阶跃点; P＝max{P1,P2}; If (P2>P1) xn－1=1; else xn－1=0; 回溯确定xn－2,xn-3,,x0; }

7.6.5 性能分析 在最坏情况下，算法的空间复杂度是O(2n)。 在最坏情况下，算法的时间复杂度是O(2n)。

7.7 流水作业调度

7.7.1 问题描述 假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J={J0,J1,…,Jn1}和m台设备P={P1,P2,…,Pm}。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0i<n。如何将这nm个任务分配给这m台设备，使得这n个作业都能顺利完成。这就是流水线作业调度(flow shop schedule)问题。

例7－10 设有三台设备两个作业，每个作业包含三项任务。完成这些任务的时间由矩阵M给定。

作业i的完成时间fi(S)是指在调度方案S下，该作业的所有任务都已完成的时间。 完成时间F(S)是所有作业都完成的时间。 平均流动时间(mean flow time)MFT(S)定义为：

一组给定的作业的最优完成时间是F(S)的最小值。 OFT表示指非抢先调度最优完成时间 POFT表示抢先调度最优完成时间。 OMFT表示非抢先调度最优平均完成时间， POMFT表示抢先调度最优平均完成时间。 本节只讨论当m=2时获得OFT的调度方案的算法，这就是双机流水作业调度问题。

双机流水作业调度描述为：设有n个作业的集合{0，1，…，n-1}，每个作业都有两项任务要求在2台设备P1和P2组成的流水线上完成加工。每个作业加工的顺序总是先在P1上加工，然后在P2上加工。P1和P2加工作业i所需的时间分别为a i和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在设备P1上开始加工，到最后一个作业在设备P2上加工完成所需的时间最少。即求使F(S)有最小值的非抢先调度方案S。

7.7.2 动态规划法求解 重要结论（可证明）：在两台设备的情况下，存在一个最优非抢先调度方案，使得在P1和P2上的作业完全以相同次序处理（若m>2则不然）。

定理7－3 流水作业调度问题具有最优子结构的性质。  =((0),(1),…,(k-1)) g (S, t) 递推关系： g(N,0)=min{ai+g(N-{i},bi )}; i属于{0,1,…,N-1}. 对任意的集合S和I (i属于S）： g(S,t)=ai+g(S-{i},t’), t’=bi+max{t-ai,0}

如果在调度方案的作业排列中，作业i和j满足min{bi,aj}min{bj,ai}，则称作业i和j满足Johnson不等式。

最优调度求解方案 可以设计下列作业排列方法。这样做能得到最优调度方案 (1)如果min{a0,a1,…,an1, b0,b1,…,bn1}是ai，则ai应是最优排列的第一个作业； (2)如果min{a0, a1, …, an-1, b0, b1,…, bn1}是bj，则bj应是最优排列的最后一个作业； (3) 继续（1）和（2）的做法，直到完成所有作业的排列。

所以最优解为：((0),(1),(2),(3)) ＝（0,2,3,1）。 例7－11设n＝4，（a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。 设 =((0),(1),(2),(3))是最优作业排列。 先将任务按处理时间的非减次序排列成： （b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15) 先选 b1，将其加在最优作业排列的最后，故(3)=1 再选a0，应加在最优作业排列的最前面，故 (0)=0 考察a1和b0，因作业1和0已调度， 接着考察a2，应有(1)=2，再考察b2和a3，令(2)=3。 所以最优解为：((0),(1),(2),(3)) ＝（0,2,3,1）。

7.7.3 Johnson算法 Johnson算法具体描述如下： 设a[i]和b[i]，0i<n分别为作业i在两台设备上的处理时间。建立由三元组（作业号,处理时间,设备号）组成的三元组表d。 对三元组表按处理时间排序，得到排序后的三元组表d。 对三元组表的每一项d[i]，0i<n，从左和右两端生成最优作业排列c[j], 0j<n，c[j]是作业号。如果d[i]的设备号为1，则按从左向右顺序将作业i置于c的左端第一个空位，否则按从右向左的顺序置于c的右端第一个空位。

【程序7－12】Johnson算法 //三元组结构 struct Triplet{ int operator <(Triplet b)const { return t<b.t;} int jobNo, t, ab; };

void FlowShop(int n, int *a,int *b,int *c) { Triplet d[mSize]={{0,0,0}}; for(int i=0;i<n;i++) if(a[i]<b[i]) { d[i].jobNo=i; d[i].ab=0; d[i].t=a[i]; } else { d[i].jobNo=i; d[i].ab=1; d[i].t=b[i]; Sort(d,n); //n个元素排序，O(nlogn) int left=0, right=n-1; //指示左右两端首个空位 for (i=0;i<n;i++) if(d[i].ab==0) c[left++]=d[i].jobNo; else c[right--]=d[i].jobNo;

Johnson算法的时间取决于对作业集合的排序，因此，在最坏情况下算法的时间复杂度为O(nlogn)，所需的空间复杂度为O(n)。 （a0,a1,a2,a3）=(3,4,8,10) （b0,b1,b2,b3）=(6,2,9,15)。 Johnson算法的时间取决于对作业集合的排序，因此，在最坏情况下算法的时间复杂度为O(nlogn)，所需的空间复杂度为O(n)。

动态规划法 小结 求最优化问题 与分治法、贪心法比较 最优子结构原理 递推关系 分析子问题的重叠性 自底向上计算（最优解值） 构造最优解 动态规划法 小结 求最优化问题 最优子结构原理 递推关系 分析子问题的重叠性 自底向上计算（最优解值） 构造最优解 与分治法、贪心法比较 备忘录方法