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

文档介绍：矩阵连乘 2、最长公共子序列 3、最大子段和
凸多边形最优三角剖分 5、流水作业调度
6、0-1背包问题 7、最优二叉搜索树
实验目的
掌握动态规划法的基本思想和算法设计的基本步骤。
实验内容与源码
矩阵连乘
#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);
return 0;
}
运行结果
最长公共子序列
#include<cstring>
#include<iostream>
#define N 100
using namespace std;
//str1存储字符串x,str2存储字符串y
char str1[N],str2[N];
//lcs存储最长公共子序列
char lcs[N];
//c[i][j]存储str1[1...i]与str2[1...j]的最长公共子序列的长度
int c[N][N];
//flag[i][j]==0为str1[i]==str2[j]
//flag[i][j]==1为c[i-1][j]>=s[i][j-1]
//flag[i][j]==-1为c[i-1][j]<s[i][j-1]
int flag[N][N];
//求长度
int LCSLength(char *x, char *y)
{
int i,j;
//分别取得x,y的长度
int m = strlen(x);
int n = strlen(y);
for(i=1;i<=m;i++)
c[i][0] = 0;
for(i=0;i<=n;i++)
c[0][i] = 0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
if(x[i-1]==y