《动态规划——矩阵连乘》由会员分享,可在线阅读,更多相关《动态规划——矩阵连乘(3页珍藏版)》请在金锄头文库上搜索。
代码:#includeusing namespace std;const int MAX = 100;/p 用来记录矩阵的行列,main 函数中有说明/mij用来记录第 i 个矩阵至第 j 个矩阵的最优解/s用来记录从哪里断开的才可得到该最优解int pMAX+1,mMAXMAX,sMAXMAX;int n;/矩阵个数void matrixChain()for(int i=1;in;for(int i=0;ipi;/测试数据可以设为六个矩阵分别为/A130*35,A235*15,A315*5,A45*10,A510*20,A620*25/则 p0-6=30,35,15,5,10,20,25/输入:6 30 35 15 5 10 20 25matrixChain();traceback(1,n);/最终解值为 m1n;coutj,则 mij=minmik+mk+1j+pi-1XpkXpj,其中 k,在 i 与 j之间游荡,所以 i=kj ;代码实现时需要注意的问题:计算顺序!因为你要保证在计算 mij查找 mik和 mk+1j的时候,mik和 mk+1j已经计算出来了。观察坐标的关系如图:所以计算顺序如上右图:相应的计算顺序对应代码为 13-15 行m1n即为最终求解,最终的输出想为(A1(A2 A3)(A4 A5)A6)的形式,不过没有成功,待思考.