动态规划

矩阵链相乘：求出计算乘积A₁A₂...A_n所需标量乘法最少的方案

算法方法简介：我们使用以空间换取时间的方法，采用自底向上表格法代替递归式。算法使用一个辅助表m[1...n][1..n]保存计算矩阵A_i..j所需标量乘法的最小次数，用s[1..n][2...n]记录最优值的分割点，然后使用表s构造最优解。其中m[i,j]=m[i,k]+m[k+1,j]+p_i-1p_kp_j，其中k是分割点，它只有j-i种可能的取值：k=i,i+1,...j-1。

代码1：

View Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define ArrS 6
 4 
 5 int matrix_value(int i,int j,int m[][ArrS+1],int Num1,int p[],int s[][ArrS+1]);
 6 void show(int s[][ArrS+1],int i,int j);
 7 
 8 int main()
 9 {
10 int s[ArrS+1][ArrS+1]={0}; 
11 int m[ArrS+1][ArrS+1]={0};
12 int p[ArrS+1]={30,35,15,5,10,20,25};
13 
14 int i,j,L;
15 
16 for(j=0;j<ArrS;j++)
17 for(i=1;i+j<=ArrS;i++)
18 m[i][i+j]=matrix_value(i,i+j,m,ArrS+1,p, s);
19 
20 
21 printf("Show the position[i][j]:\n"); 
22 for(i=1;i<=ArrS;i++)
23 {
24 for (j=1;j<=ArrS;j++)
25 printf("%d ",s[i][j]);
26 printf("\n");
27 }
28 
29 
30 printf("\n\nThe path is:\n");
31 show(s,1,6);
32 
33 system("PAUSE"); 
34 return 0;
35 }
36 
37 int matrix_value(int i,int j,int m[][ArrS+1],int Num1,int p[],int s[][ArrS+1])
38 {
39 if(j==i)
40 {
41 s[i][j]=i;
42 return 0;
43 }
44 
45 int k,min;
46 min=p[i-1]*p[i]*p[j]+m[i+1][j];
47 s[i][j]=i;
48 for(k=i+1;k<j;k++)
49 if(min>p[i-1]*p[k]*p[j]+m[i][k]+m[k+1][j])
50 {
51 min=p[i-1]*p[k]*p[j]+m[i][k]+m[k+1][j];
52 s[i][j]=k;
53 }
54 
55 return min;
56 }
57 
58 void show(int s[][ArrS+1],int i,int j)
59 //用递归的方法去显示完整路径，调用的方式是 show(1，n）
60 {
61 if (j<=i)
62 return;
63 int a;
64 a=s[i][j];
65 printf("position[%d][%d]=%d \n",i,j,s[i][j]);
66 show(s,i,a);
67 show(s,a+1,j);
68 }

代码2：

View Code

 1 #include <vector>
 2 #include <iostream>
 3 using namespace std;
 4 int m[100][100];
 5 int vz[100][100];
 6 class MattrixCM
 7 {
 8 public:
 9     int cal(vector<int> v)//计算最少乘法次数
10     {
11         int i=0,n=v.size()-1,j=0;
12         int l,k,temp;
13         for(i=0;i<n;i++)
14             m[i][i]=0;
15         for(l=2;l<=n;l++)
16         {
17             for(i=0;i<=n-l;i++)
18             {
19                 j=i+l-1;
20                 for(k=i;k<j;k++)
21                 {
22                     if(k==i)
23                     {
24                         m[i][j]=m[i][k]+m[k+1][j]+v[i]*v[i+1]*v[j+1];
25                         vz[i][j]=k;
26                     }
27                     else
28                     {
29                         temp=m[i][k]+m[k+1][j]+v[i]*v[k+1]*v[j+1];
30                         if(temp<m[i][j])
31                         {
32                             m[i][j]=temp;
33                             vz[i][j]=k;
34                         }
35                     }
36                 }
37             }
38         }
39         return m[0][n-1];
40     }
41     void printResult(int i,int j)//输出最优加括号方式
42     {
43         if(i==j)
44             cout<<"A"<<i+1;
45         else
46         {
47             cout<<"(";
48             printResult(i,vz[i][j]);
49             printResult(vz[i][j]+1,j);
50             cout<<")";
51         }
52 
53     }
54 };
55 int main()
56 {
57     vector<int> v;
58     v.push_back(30);v.push_back(35);v.push_back(15);v.push_back(5);
59     v.push_back(10);v.push_back(20);v.push_back(25);
60     MattrixCM mcm;
61     cout<<mcm.cal(v)<<endl;
62     mcm.printResult(0,5);
63     cout<<endl;
64     system("pause");
65     return 0;
66 }