动态规划----矩阵连乘问题.doc

动态规划----矩阵连乘问题 动态规划法是解决问题的一种方法。它不规定为了得到结果需如何将问题划分为子问题的固定方法，而是按不同输入给出问题的具体实例的子问题划分方法，然后再进行运算、解答问题。 矩阵连乘问题的主要思想如下： 1）设置大小为连乘个数的方阵 2）主对角线上方各元素Di,j(ij)表示矩阵Mi连乘到Mj的最小工作量 3）下方元素Di,j(ij)记录获得该最小工作量矩阵分组的第一组的最后一个矩阵的序列号 最后通过下方元素可知最终结果的分组方式。 算法描述为： 1）读入n, 即矩阵的个数; 2）读入n+1个数, 即n个矩阵的行数和列数, 将它们存入数组r中; 3）将d主对角线元素置为零; 4）求出d矩阵的其它元素的数值; 5）给出n个矩阵的结合方式. 程序源代码： #define MAXINT 1000 int D[10][10],R[11]; void print(int i, int j) { int k; if(i==j) printf(M%d,i); else if (i+1==j) printf(M%d,M%d,i,j); else { k =D[j][i]; printf( (); print(i,k); print(k+1, j); printf()); } } DM(int N) { int I,J,K,T; for(I=1;IN-1;I++) for(J=1;JN-1;J++) { D[J][J+1]=MAXINT; for(K=0;KI-1;K++) { T=D[J][J+K]+D[J+K+1][J+1]+R[J-1]*R[J+K]*R[J+1]; if(TD[J][J+1]) { D[J][J+1]=T; D[J][J+1]=J+K; } } } } main() { int flag=1,N,i; char c; printf(e------exit i--------continue\n); while(flag==1) {scanf(%c,c); switch(c) { case i: flag=1; printf(Please Input The Data:\n); printf(The value of matrix: N=); scanf(%d,N); for(i=0;iN;i++) { printf(R[i]=,i); scanf(%d,R[i]); } for(i=1;iN;i++) D[i][i]=0; DM(N); print(1,N+1); break; case e: flag=0;break; } } } 运行结果： 动态规划----有向图的最短路径问题 include iostream.h int const m=4; struct node { int flag[m]; float cost; }; void all_paths(node COST[m][m],node A[m][m],int n) { int i,j,k; for(i=0;in;i++) for(j=0;jn;j++) { A[i][j].cost=COST[i][j].cost; for(k=0;kn;k++) A[i][j].flag[k]=0; } for(k=0;kn;k++) { for(i=0;in;i++) for(j=0;jn;j++) { if(A[i][j].cost(A[i][k].cost+A[k][j].cost))