计算最优值.cpp

用C++实现矩阵连乘问题

#include<iostream.h>
#include"make2db.h"
int r[7]={0,10,5,1,10,2,10};
int **kay,**c;
int C(int i,int j)
{ //返回c(i,j) 并计算kay(i,j)=kay[i][j]
  //避免重复计算
  //检查是否已计算过
	if(c[i][j]>0) return c[i][j];
	//若未计算,则进行计算
	if(i==j) return 0; //一个矩阵的情形
	if(i==j-1)
	{//两个矩阵的情形
		kay[i][i+1]=i;
		c[i][j]=r[i]*r[i+1]*r[i+2];
		return c[i][j];
	}
	//多于两个矩阵的情形
	//设u为k = i 时的最小值
	int u=C(i,i)+C(i+1,j)+r[i]*r[i+1]*r[j+1];
	kay[i][j]=i;
	//计算其余的最小值并更新u
	for(int k=i+1; k<j;k++)
	{
		int t=C(i,k)+C(k+1,j)+r[i]*r[k+1]*r[j+1];
		if(t<u)
		{ // 比最小值还小
			u=t;
			kay[i][j]=k;
		}
	}
	c[i][j]=u;
	return u;
}
void Traceback(int i,int j,int **kay)
{ //输出计算Mi j 的最优方法
	if(i==j) return;
	Traceback(i,kay[i][j],kay);
	Traceback(kay[i][j]+1,j,kay);
	cout<<"Multiply M"<<i<<","<<kay[i][j];
	cout<<"and M"<<(kay[i][j]+1)<<","<<j<<endl;
}
void main()
{
	int q=5;
	int i,j;
	Make2DArray(c,q+1,q+1);
	Make2DArray(kay,q+1,q+1);
	for(i=1;i<=q;i++)
		for(j=i;j<=q;j++)
			c[i][j]=0;
		cout<<"Optimal cost is"<<C(1,q)<<endl;
		cout<<"kay matrix is"<<endl;
		for(i=1;i<=q;i++)
		{
			for(j=1;j<=i;j++)
				cout<<0<<' ';
			for(j=i+1;j<=q;j++)
				cout<<c[i][j]<<' ';
			cout<<endl;
		}
		cout<<"kay matrix is"<<endl;
		for(i=1;i<=q;i++)
		{
			for(j=1;j<=i;j++)
				cout<<0<<' ';
			for(j=i+1;j<=q;j++)
				cout<<kay[i][j]<<' ';
			cout<<endl;
			Traceback(1,q,kay);
		}
}