《算法设计与分析实验-动态规划》由会员分享,可在线阅读,更多相关《算法设计与分析实验-动态规划(2页珍藏版)》请在金锄头文库上搜索。
1、#include #include using namespace std; #define SIZE 6 /控制参与连乘矩阵的个数 int mSIZESIZE,sSIZESIZE;void MatrixChain(int p,int n) /用来产生数组 m 和 s,是关键部分 for(int a=0;an;a+) maa=0; for(int r=2;r=n;r+)for(int i=0;in-r+1;i+)int j=i+r-1;mij=mi+1j+pi*pi+1*pj+1;sij=i+1;for(int k=i+1;kj;k+)int t=mik+mk+1j+pi*pk+1*pj+1;
2、if(tmij)mij=t;sij=k+1; int Traceback(int i,int j) /找出 s 数组中记录的最优断开点 if(i=j) return -1; Traceback(i,sij-1); Traceback(sij,j); cout“包含矩阵 A“sij; cout“的部分与包含矩阵 A“(sij+1)“的部分结合,放在一个括号中“endl; return 0; void main() int pSIZE+1=10,20,25,15,5,10,25; /p 记录矩阵的行列数MatrixChain(p,SIZE); cout“输出 m 矩阵为:“endl; for(int i=0;iSIZE;i+)for(int j=0;jSIZE;j+)coutsetw(6)mij“ “;coutendl; coutendlendl; cout“输出 s 矩阵为:“endl; for(int a=0;aSIZE;a+) for(int b=0;bSIZE;b+)coutsetw(6)sab“ “;coutendl; coutendlendl; Traceback(0,5);