动态规划--矩阵相乘.cpp

动态规划算法

/*********************************************************
programmer: linpder
time:  05.10.22
topic: 动态规划－－矩阵相乘。
  动态规划的问题还有很多，备忘录方法，最长公共子序列，
凸多边形的最优三角部分等。
*********************************************************/
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>

#define MAX  32767   //定义一个最大值

int a[11];   //存储在连乘时断开的位置.

void find(int pos[11][11],int s,int e,int &i)
        //用递归算法求出断开的位置.
{
	int b;
	b=pos[s][e];
	if(b<s)return ;  //如果b的值小于s的，退出
	if(b>e)return ;  //如果b的值大于s的，退出
	if(e==s+1)return ; //如果e只比s大一，退出
	a[i]=b;
	i++;
	
	find(pos,s,b,i);	
	find(pos,b+1,e,i);
}

int main()
{
	int N,p[11];
	int i,j,k,g;
	int temp[11][11],pos[11][11],temp1;

	printf("请输入相乘矩阵的个数(不大于10):"); 
	scanf("%d",&N);   //总共有 N个矩阵相乘
	printf("输入 %d 个整数表示这 %d 个矩阵的阶数:\n",N+1,N);
	for(i=0;i<=N;i++)
		scanf("%d",&p[i]);  //这N个矩阵的阶数

	printf("\n计算得到的结果为如下所示:\n");
	for(i=1;i<=N;i++)
		temp[i][i]=0; 
	for(g=2;g<=N;g++)
		for(i=1;i<=N-g+1;i++)
		{
			j=i+g-1; 
			temp[i][j]=MAX;
			for(k=i;k<=j-1;k++)  //断点
			{
				temp1=temp[i][k]+temp[k+1][j]+p[i-1]*p[k]*p[j];
				if(temp1<temp[i][j])
				{
					temp[i][j]=temp1; //保存Ai..j相乘的最优值。
					pos[i][j]=k;  //保存矩阵Ai..j的最优断开位置。
				}
			}
        //输出计算过程的结果
			cout<<"temp["<<i<<"]["<<j<<"]="<<setw(5)<<temp[i][j];
			cout<<"        pos["<<i<<"]["<<j<<"]="<<pos[i][j]<<endl;
			if(i==N-g+1)
				cout<<endl;  
		}
	
    i=0;
	find(pos,1,N,i);  //找出每个断开位置。

	int n=i;

	printf("输入的矩阵连乘时断开的位置如下:\n");
	for(j=0;j<n;j++)
		printf("%d ",a[j]);

	printf("\n所以我们可以得到加括号后的式子为:(A1*(A2*A3))(A4*(A5*A6))\n");
      //输入为规定时的情况，自己定的 ^_^！

	printf("\n采用动态规划算法得出的计算结果为: ");
	printf("%d\n",temp[1][N]);

	getch();
	return 0;
}