matrixchain.cpp

动态规划:矩阵连乘问题的模拟程序 参考清华王晓东的<算法设计与分析>

# include <stdio.h>
# include <iostream.h>

# define MATRIX_NUM 4

void matrixChain(int p[MATRIX_NUM+1],int m[MATRIX_NUM+1][MATRIX_NUM+1],int s[MATRIX_NUM+1][MATRIX_NUM+1]);

	int p[MATRIX_NUM+1]={15,2,10,5,3};
	int m[MATRIX_NUM+1][MATRIX_NUM+1];
	int s[MATRIX_NUM+1][MATRIX_NUM+1];

void main()
{

	matrixChain(p,m,s);

	cout<<"m:"<<endl;
	for (int i=1;i<MATRIX_NUM+1;i++)
	{
		for (int j=1;j<MATRIX_NUM+1;j++)
			printf("%d	",m[i][j]);
		printf("\n");
	}
	cout<<"s:"<<endl;
	for (i=1;i<MATRIX_NUM+1;i++)
	{
		for (int j=1;j<MATRIX_NUM+1;j++)
			printf("%d	",s[i][j]);
		printf("\n");
	}
}

void matrixChain(int p[MATRIX_NUM+1],int m[MATRIX_NUM+1][MATRIX_NUM+1],int s[MATRIX_NUM+1][MATRIX_NUM+1])
{
	int n=MATRIX_NUM;
	for (int i=0;i<=n;i++) m[i][i]=0;
	for (int r=2;r<=n;r++)
		for (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=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;
				}
			}
		}
}