juzhenliancheng.rar_juzhenliancheng

#include <iostream.h> #define INT_MAX 2147483647 #include <iomanip.h> /************************************************************** *order[i]:矩阵Ai的列数或Ai-1的行数 *weight[i][j]:纪录Ai - Aj的矩阵链乘的最小代价 *breakpoint[i][j]:纪录Ai - Aj之间得到最小链乘代价时的分割点 **************************************************************/ void MatrixChainOrder(int* order, int** weight, int** breakpoint,int length) { int i, j, k, len, q; for(i=0; i<length; i++) weight[i][i] = 0; for(len=2; len<=length; len++) //len为矩阵链的长度 { for(i=0; i<(length-len+1); i++) { j = i + len - 1; weight[i][j] = INT_MAX; //计算Ai - Aj最优代价 for(k=i; k<j; k++) { q = weight[i][k] + weight[k+1][j] +order[i]*order[k+1]*order[j+1]; if(q < weight[i][j]) { weight[i][j] = q; breakpoint[i][j] = k; } } } } } void PrintOptimalParens(int** breakpoint, int i, int j) { if(i == j) cout<<" A"<<i<<" "; else { cout<<"("; PrintOptimalParens(breakpoint, i, breakpoint[i][j]); PrintOptimalParens(breakpoint, breakpoint[i][j]+1, j); cout<<")"; } } void main() { int length; cout<<"******************************************************************"<<endl; cout<<" 矩阵链乘动态规划问题 "<<endl; cout<<"******************************************************************"<<endl; cout<<"请输入矩阵链的长度："; cin>>length; int* order=new int[length+1]; cout<<"请输入矩阵链的行列数:"<<endl; for(int i=0;i<=length;i++) { cin>>order[i]; } int** weight=new int*[length]; for(i=0;i<length;i++) { weight[i]=new int[length]; } int** breakpoint=new int*[length]; for(i=0;i<length;i++) { breakpoint[i]=new int[length]; } MatrixChainOrder(order, weight, breakpoint,length); cout<<"该矩阵链操作次数最少的加括号输出表达式为:"<<endl; PrintOptimalParens(breakpoint, 0, length-1); cout<<endl; cout<<"输出weight矩阵："<<endl; for(i=0;i<length;i++) for(int j=0;j<length;j++) { if(weight[i][j]<0) weight[i][j]=0; cout<<setw(6)<<weight[i][j]; if(j==length-1) cout<<endl; } cout<<"输出breakpoint矩阵："<<endl; for(i=0;i<length;i++) for(int j=0;j<length;j++) { if(breakpoint[i][j]<0) breakpoint[i][j]=-1; cout<<setw(6)<<breakpoint[i][j]; if(j==length-1) cout<<endl; } }