计算机算法设计与分析【王晓东-电子工业出版社-2版】-第3章文库.ppt

上海金融学院信息管理系 第3章 动态规划 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 #include stdafx.h #include iostream.h void MatrixChain(int* p,int n,int m[][7],int s[][7]); void Traceback(int i,int j,int s[][7]); int main(int argc, char* argv[]) { int n=6; int m[6][6]; int s[6][6]; int p[7]; for (int i=0;i=n;i++) {cout\n 请输入正整数p(i); cinp[i]; } MatrixChain(p,n,m,s); Traceback(1,n,s); return 0; } #include stdafx.h #include iostream.h void MatrixChain(int* p,int n,int m[][6],int s[][6]); void Traceback(int i,int j,int s[][6]); int main(int argc, char* argv[]) { int n=6; int m[6][6]; int s[6][6]; int p[7]; for (int i=0;i=n;i++) {cout\n 请输入正整数p(i); cinp[i]; } for (int ii=0;ii=n;ii++) coutp[ii] ; coutendlendlendl; MatrixChain(p,n,m,s); //coutnendl; Traceback(1,6,s); return 0; } #include stdafx.h #include iostream.h int LookupChain(int p[],int i,int j,int m[][6],int s[][6]); int MMatrixChain(int p[],int n,int m[][6],int s[][6]); void Traceback(int i,int j,int s[][6]); int main(int argc, char* argv[]) { int n=6; int m[6][6]; int s[6][6]; int p[7]; for (int i=0;i=n;i++) {cout\n 请输入正整数p(i); cinp[i]; } MMatrixChain(p,n,m,s); Traceback(1,6,s); return 0; } int MMatrixChain(int p[],int n,int m[][6],int s[][6]) { for (int i = 1; i = n; i++) for (int j = i; j = n; j++)m[i][j] = 0; return LookupChain(p,1,n,m,s); } 例如：设所给的2个序列为X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A} 由算法LCSLength和LCS计算出的结果如图3-3所示。 计算最优值 #include stdafx.h #include iostream.h void LCSLength(int m,int n,char *x,char *y,int c[][7],int b[][7]); void LCS(int i,int j,cha