动态规划一.矩阵连乘

 1 #include<iostream>
 2 using namespace std;
 3 int const M=7;
 4 void MATRIX_CHAIN_ORDER(int *p,int Length,int m[][M],int s[][M])
 5 {
 6     int q,n=Length-1;
 7     for(int i=1;i<=n;i++) m[i][i]=0;//只有一个矩阵时，无需计算 
 8     for(int l=2;l<=n;l++)     /* 矩阵链的长度 */
 9     {
10         for(int i=1;i<=n-l+1;i++) //n-r+1是最后l链的起始位置，左边界i(若l=2 那么最后一条链的起始位置就是倒数第二个位置） 
11         {
12             int j=i+l-1; /* 等价于 l=j-i+1 */
13             m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
14             s[i][j]=i;
15             for(int k=i+1;k<=j-1;k++)//找出不同长度链的所有数乘次数最小 分割点s[i][j] 
16             {
17                 q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
18                 if(q<m[i][j])
19                 {
20                     m[i][j]=q;
21                     s[i][j]=k;//记录分割位置（i<=k<j） 
22                 }
23             }
24         }
25     }
26 }
27 void PRINT_OPTIMAL_PARENS(int s[][M],int i,int j)//牢记s[i][j]是数乘次数m[i][j]最小时的分割点 
28 {
29     if(i == j) cout<<"A"<<i;
30     else
31     {
32         cout<<"(";
33         PRINT_OPTIMAL_PARENS(s,i,s[i][j]);
34         PRINT_OPTIMAL_PARENS(s,s[i][j]+1,j);
35         cout<<")";
36     }
37 }
38 int main()
39 {
40    int p[M]={30,35,15,5,10,20,25};
41    int m[M][M],s[M][M];
42    MATRIX_CHAIN_ORDER(p,M,m,s);
43    cout<<"当n=6时最优解为: 
"<<m[1][6];
44    cout<<"
括号化方案为：
"; 
45    PRINT_OPTIMAL_PARENS(s,1,6);
46    return 0;
47 }

问题描述：
矩阵连乘找最小数乘次数以及组合方式。
矩阵Ai的维数为p[i-1]*p[i].//详情见课本p48
p[i-1]*p[k]*p[j] 是前面两个子矩阵的相乘数乘次数。
例如：
计算{A1，A2,A3}的连乘积的例子。设这三个矩阵的维数分别为10*100，100*5，5*50，若按第一种加括号方式（（A1A2）A3）计算，那么数乘次数需要10*100*5+10*5*50=7500

动态规划 一.矩阵连乘

动态规划一.矩阵连乘