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

文档介绍：该【动态规划算法实验报告 】是由【秋江孤影】上传分享，文档一共【22】页，该文档可以免费在线阅读，需要了解更多关于【动态规划算法实验报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。动态规划算法实验报告
作者:
日期:
实验标题
实验目的
实验内容
与源码
1、矩阵连乘 2、最长公共子序列 3、最大子段和
4、凸多边形最优三角剖分 5、流水作业调度
6、0—1背包问题7、最优二叉搜索树
掌握动态规划法的基本思想和算法设计的基本步骤。
1、矩阵连乘
#include<iostream>
#include<cstdlib>
usingnamespacestd;
constintsize=4;
//ra,ca和rb,cb分别表示矩阵A和B的行数和列数
voidmatriMu1tiply(inta[][4],intb[][4],intc[][4],intra,intca,intrb,intcb){
if(ca!=rb)cerr<<”矩阵不可乘”;
for(inti=0;i<ra;i++)
for(intj=0;j<cb;j++)
{
intsum=a[i][0]*b[0][j];
for(intk=1;k<ca;k++)
sum+=a[i][k]大b[k][j];c[i][j]=sum;
}
}
voidMatrixChain(int*p,intn,intm[][4],ints[][4]){
for(inti=1;i<=n;i++)m[i][i]=0;//对角线
for(intr=2;r<=n;r++)//外维
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<j;k++)
{
intt=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;
}
voidTraceback(inti,intj,ints[][4])
{
if(i==j)
{
cout<<"A"<<i;
}
elseif(i+1==j)
{
cout<〈”(Ay<i〈<”A"<<j<<")";
}
e1se
{
cout<<"(”;
Traceback(i,s[i][j],s);
Traceback(s[i][j]+1,j,s);
cout<<")";
}
}
intmain()
{
intw;
coutVV”矩阵个数:";
cin>>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"«iv<"维数:";
cin>>p[i-1]>>p[i];
if(p[i-1]!=m)
{
cout<<endl<<"维数不对,矩阵不可乘!"vvendl;
exit(1);
}
}
Traceback(1,w,s);
return0;
运行结果
!■任慎法\<:。艮\泡1车连乘1咨巳 l_[=^ii_B
桐时数:3
而人矩降垃维数:E3输恐邛三监维数:如愉熟邱三M维数:45((A1A2)蜘*
2、最长公共子序列
#include<cstring>
#include<iostream>
#defineN100
usingnamespacestd;
//str1存储字符串x,str2存储字符串y
charstr1[N],str2[N];
//lcs存储最长公共子序列
charlcs[N];
//c[i][j]存储str1[1...i]与str2[l...j]的最长公共子序列的长度intc[N][N];
//flag[i][j]==0为str1[i]==str2[j]
//flag[i][j]==1为c[iT][j]>=s[i][j-1]
//flag[i][j]==-1为c[i-1][j]<s[i][j-1]
intflag[N][N];
//求长度
intLCSLength(char*x,char*y)
{
inti,j;
//分别取得x,y的长度
intm=strlen(x);
intn=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-l][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;
}
eIse
{
c[i][j] =c[i][j-1];
flag[i][j]=-1;
}
}
returnc[m][n];
}
〃求出最长公共子序列
char大getLCS(char大x,char大y,int1en,char大1cs){
inti=strlen(x);
intj=strlen(y);
while(i&&j)
{
if(flag[i][j]==0)
{
lcs[--1en]=x[i-1];
i--;
j--;
}
elseif(flag[i][j]==1)
i—-;
else
j--;
}
returnlcs;
}
intmain()
{
inti;
cout<<"请输入字符串x:"<〈end1;
cin>>str1;
cout«"请输入字符串y:"«end1;
cin»str2;
int1csLen=LCSLength(strl,str2);
cout<<"最长公共子序列长度:"«lcsLen<<endl;
char*p=getLCS(str1,str2,lcsLen,1cs);
coutVv”最长公共子序列为:”;
for(i=0;i<lcsLen;i++)
cout«lcs[i]«"
retum0;}
运行结果
3、最大子段和
//分治法求最大子段和
#include<iostream>
usingnamespacestd;
intMaxSubSum(int大a,int1eft,intright)
{
intsum=0;
if(1eft==right)sum=a[left]>0?a[left]:0;
else
{
intcenter=(left+right)/2;
//最大子段和在左边
int1eftsum=MaxSubSum(a,1eft,center);
〃最大子段和在右边
intrightsum=MaxSubSum(a,center+1,right);
〃最大子段和在中间
intsi=0;
intlefts=0;
for(inti=center;i>=left;i--)
lefts+=a[i];
if(lefts>s1)s1=lefts;
}
ints2=0;
intrights=0;
for(inti=center+1;i<=right;i++){
rights+=a[i];
if(rights>s2)s2=rights;
}
sum=s1+s2;〃前后子段和相加
//判断最大子段和
if(sum>leftsum)sum=leftsum;
if(sum>rightsum)sum=rightsum;
}
returnsum;
}
intMaxSum(int大a,intn)
{
returnMaxSubSum(a,1,n-1);
}
intmain()
{
inta[8]={2,-3,-5,4,1,7,1,-5};
cout<<"最大子段和为:"<<MaxSum(a,8);
return0;
}
〃动态规划法
#include<iostream>
usingnamespacestd;
intMaxSum(int*a,intn)
{
intsum=0,b=0;
for(inti=1;i<n;i++)//此处不能=n,
{
if(b>0)b+=a[i];
elseb=a[i];
if(b>sum)sum=b;
}
returnsum;
}
intmain()
{
inta[8]={2,-3,-5,4,1,7,1 5};
cout<<"最大子段和为:"vVMaxSum(a,8);
retum0;
}
运行结果
L水■- sLJUJ |Ll[|L-^J||G
最大T思和
Processieti_nrtied0(0x0)executionTim日::mykeytoccntmue.
4、凸多边形最优三角剖分
include<iostream>
#include<cmath>
include<cstdlib>
#defineN50
usingnamespacestd;
structpoint
{
intx;
inty;
};
intdistance(pointX,pointY)〃两点距离
{
intdis= (-)大(—)+(-)*(—);
return(int)sqrt(dis);
}
intw(pointa,pointb,pointc)〃权值
{
returndistance(a,b) +distance(b,c)+distance(a,c);
}
boolJudgeInput()//判断是否能构成凸多边形
{
point*v; //记录凸多边形各顶点坐标
int*total; //记录坐标在直线方程中的值
intm,a,b,c;