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

《动态规划算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验标题1、矩阵连乘2、最长公共子序列3、最大子段和4、凸多边形最优三角剖分5、流水作业调度6、0-1背包问题7、最优二叉搜索树实验目的掌握动态规划法的基本思想和算法设计的基本步骤。实验内容与源码1、矩阵连乘#include#includeusingnamespacestd;constintsize=4;//ra,ca和rb,cb分别表示矩阵A和B的行数和列数voidmatriMultiply(inta[][4],intb[][4],intc[][4],intra,intc

2、a,intrb,intcb){if(ca!=rb)cerr<<"矩阵不可乘";for(inti=0;i

3、++)//外维for(inti=1;i<=n-r+1;i++)//上三角{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k

4、i+1==j){cout<<"(A"<>w;intp[w],s[w][w];cout<<"输入矩阵A1维数：";cin>>p[0]>>p[1];for(inti=2;i<=w;i++){intm=p[i-1];cout<<"输入矩阵A"<

5、>p[i-1]>>p[i];if(p[i-1]!=m){cout<#include#defineN100usingnamespacestd;//str1存储字符串x，str2存储字符串ycharstr1[N],str2[N];//lcs存储最长公共子序列charlcs[N];//c[i][j]存储str1[1

6、...i]与str2[1...j]的最长公共子序列的长度intc[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]

7、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[j-1]){c[i][j]=c[i-1][j-1]+1;flag[i][j]=0;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];flag[i][j]=1;}else{c[i][j]=c[i][j-1];flag[i][j]=-1;}}returnc[m][n];}//求出最长公共子序列char*ge

8、tLCS(char*x,char*y,intlen,char*lcs){inti=strlen(x);intj=strlen(y);while(i&&j){if(flag[i][j]==0){lcs[--len]=x[i-1];i--;j--;}elseif(flag[i][j]==1)i--;elsej--;}returnlcs;}intmain(){inti;cout<<"请输入字