1.cpp

用动态规划解矩阵连乘问题

#include<iostream>
#include<iomanip>
using namespace std;
int matrixchain(int p[]) //计算最优值
{
	int m[10][10]={0};
	int s[10][10]={0};
	int n=5;
	for(int i=1;i<=n;i++)m[i][i]=0;
	for(int r=2;i<=n;r++)
       for(int i=1;i<=n-r+1;i++)
	   {
		   int j=i+r-1;
		   m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
		   s[i][j]=i;
		   for(int k=i+1;k<j;k++){
				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(t<m[i][j]){
					m[i][j]=t;
					s[i][j]=k;
				}
		   }
		   return s[i][j];
	   }
		   /*for(i=1;i<=6;i++)
		   {
			   for(int j=1;j<=6;j++)
				   cout<<m[i][j]<<setw(10);
		   }
		cout<<endl;
     for(i=1;i<=6;i++)
		   {
			   for(int j=1;j<=6;j++)
				   cout<<s[i][j]<<setw(10);
		   }*/
	// return s[i][j];
}
void trackback(int i,int j,int s[][])   //构造最优解
{
	if(i==1)return;
	trackback(i,s[i][j],s);
	trackback(s[i][j]+1,j,s);
		cout<<"Multiply A"<<i<<" ,"<<s[i][j];
	    cout<<"and A"<<(s[i][j]+1)<<" ,"<<j<<endl;
}

void main()
{
	int p[6]={30,35,15,5,10,20};
	matrixchain(p);
	trackback(1,6,matrixchain(p));

}