动态规划算法实验报告.pdf

文档介绍：动态规划算法实验报告
实验标题
1、矩阵连乘 2、最长公共子序列 3、最大子段和
4、凸多边形最优三角剖分 5、流水作业调度
6、0-1 背包问题 7、最优二叉搜索树
掌握动态规划法的基本思想和算法设计的基本步骤。
实验目的
、矩阵连乘
实验内容 1
#include<iostream>
与源码
#include<cstdlib>
using namespace std;
const int size=4;
//ra,ca 和 rb,cb 分别表示矩阵 A 和 B 的
行数和列数
void matriMultiply(int a[][4],int b[][4],int
c[][4],int ra ,int ca,int rb ,int cb )
{
if(ca!=rb) cerr<<"矩阵不可乘";
for(int i=0;i<ra;i++)
for(int j=0;j<cb;j++)
{
int sum=a[i][0]*b[0][j];
for(int k=1;k<ca;k++)
sum+=a[i][k]*b[k][j];
c[i][j]=sum;
}
}
void MatrixChain(int *p,int n,int
m[][4],int s[][4])
{
for(int i=1;i<=n;i++) m[i][i]=0;//对角
线
for(int r=2;r<=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;
}
}
}
}
void Traceback(int i,int j,int s[][4])
{
if(i == j)
{
cout<<"A"<<i;
}
else if(i+1 == j)
{
cout<<"(A"<<i<<"A"<<j<<")";
}
else
{
cout<<"(";
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<")";
}
}
int main()
{
int w;
cout<<"矩阵个数：";
cin>>w;
int p[w],s[w][w];
cout<<"输入矩阵 A1 维数：";
cin>>p[0]>>p[1];
for(int i=2 ; i<=w ; i++)
{
int m = p[i-1];
cout<<"输入矩阵 A"<<i<<"维
数：";
cin>>p[i-1]>>p[i];
if(p[i-1] != m)
{
cout<<endl<<"维数不对，
矩阵不可乘！"<<endl;
exit(1);
}
}
Traceback(1,w,s);
ret