问题描述
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10100，1005和550，采用（A1A2）A3，乘法次数为101005+10550=7500次，而采用A1（A2A3），乘法次数为100550+10100*50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。
求解过程
Code
#include<bits/stdc++.h>
using namespace std;
int a[10]={30, 35, 15, 5, 10, 20, 25}, m[100][100], s[100][100], n=6;
int main()
{
for(int k=1;k<=n-1;k++){//控制斜线
for(int i=1;i<=(n-k);i++){//x轴
int j=k+i;//y轴
m[i][j]=0x3f3f3f;
for(int z=j;z>i;z--){
if(m[i][z-1]+m[z][j]+a[i-1]*a[z-1]*a[j]<m[i][j]){
m[i][j]=m[i][z-1]+m[z][j]+a[i-1]*a[z-1]*a[j];
s[i][j]=z-1;
}
}
}
}
cout<<"最优解:"<<m[1][n]<<endl;
cout<<"最少数乘次数矩阵:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<m[i][j]<<"\t";
cout<<endl;
}
cout<<"------------------------------------------"<<endl;
cout<<"最佳断开位置矩阵:"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
cout<<s[i][j]<<"\t";
cout<<endl;
}
getchar();
return 0;
}
