矩阵链连乘问题:
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘 的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序 计算矩阵连乘积需要的数乘次数最少。
输入数据:共m+1行;第一行为测试数据的组数m;以后每行n+1个正 整数,表示n个矩阵的行列值。
输出:最少次数及连乘的计算次序。
样例输入:
1
5,10,4,6,10,2
样例输出:
348
(A1(A2(A3(A4A5))))
根据课本思路,首先用dp数组记录具体的次数,用s数组记录最佳的划分位置,之后遍历dp数组进行动态规划即可,此外,输入时注意好输入数据的意义,最后一个数是最后一个矩阵的列,在数据处理时应该将这个数据补上。另外,将结果输出时,需要用到之前动态规划中的s数组,根据s数组进行类似二分的输出,最后即可得到划分后的矩阵。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int m,n;
int num[1005];
int dp[1005][1005];
int s[1005][1005];
void MartixChain()
{
for(int i=1;i<=n;i++)
dp[i][i]=0;
for(int r=2;r<=n;r++)
{
for(int i=1;i<=n-r+1;i++)
{
int j=i+r-1;
dp[i][j]=dp[i+1][j]+num[i-1]*num[i]*num[j];
s[i][j]=i;
for(int k=i+1;k<j;k++)
{
int temp=dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j];
if(temp<dp[i][j])
{
dp[i][j]=temp;
s[i][j]=k;
}
}
}
}
}
void TraceBack(int i, int j){
if(i == j){
cout <<‘A’<< i;
return;
}
cout <<"(";
TraceBack(i,s[i][j]);
TraceBack(s[i][j]+1,j);
cout <<")";
}
int main()
{
scanf("%d",&m);
while(m–)
{
memset(dp,0,sizeof(dp));
int i=0;
while(1)
{
scanf("%d",&num[i]);
char c=getchar();
i++;
if(c!=’,’)
break;
}
n=i;
MartixChain();
printf("%d\n",dp[1][n-1]);
TraceBack(1,n-1);
}
return 0;
}