动态规划算法实验报告

实验标题

实验目的

1、矩阵连乘 2、最长公共子序列 3、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树

掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码

1、矩阵连乘

#include #include 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

int sum=a[i][0]*b[0][j]; for(int k=1;k

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

int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(t

m[i][j]=t; s[i][j]=k; } }

}

}

void Traceback(int i,int j,int s[][4]) {

if(i == j) {

cout<<\ }

else if(i+1 == j)

{

cout<<\ } 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\维数：\ cin>>p[i-1]>>p[i];

if(p[i-1] != m) {

cout<

Traceback(1,w,s); return 0; }

运行结果

2、最长公共子序列

#include #include #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]

//求长度

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[j-1]) {

c[i][j] = c[i-1][j-1] +1;

flag[i][j] = 0; }

else if(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; } }

return c[m][n]; }

//求出最长公共子序列

char* getLCS(char *x, char *y,int len,char *lcs) {

int i = strlen(x); int j = strlen(y); while(i&&j) {

if(flag[i][j]==0) {

lcs[--len] = x[i-1]; i--;

j--; }

else if(flag[i][j]==1) i--; else j--; } return lcs; }

int main() {

int i;

cout<<\请输入字符串x：\ cin>>str1;

cout<<\请输入字符串y：\

cin>>str2;

int lcsLen = LCSLength(str1,str2);

cout<<\最长公共子序列长度：\ char *p = getLCS(str1,str2,lcsLen,lcs); cout<<\最长公共子序列为：\ for(i=0;i

return 0; }

运行结果

3、最大子段和

//分治法求最大子段和 #include using namespace std;

int MaxSubSum(int *a,int left,int right) {

int sum=0;

if(left==right) sum=a[left]>0?a[left]:0; else

{

int center = (left+right)/2;

//最大子段和在左边

int leftsum=MaxSubSum(a,left,center);

//最大子段和在右边

int rightsum=MaxSubSum(a,center+1,right);

//最大子段和在中间 int s1=0;

int lefts=0;

for(int i=center;i>=left;i--) {