版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实验二动态规划算法基本题一:最长公共子序列问题一、实验目的与要求1、熟悉最长公共子序列问题的算法;2、初步掌握动态规划算法;二、实验题若给定序列X=xl,x2,xm,则另一序列Z=zl,z2,zk,是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有:zj=xij。例如,序列Z=B,C,D,B是序列X=A,B,C,B,D,A,B的子序列,相应的递增下标序列为2,3,5,7。给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的最长公共子序列。三、程序代码#
2、includestdlib.h#includeusingnamespacestd;voidLCSLength(intm,intn,char*x,char*y,int*c,int*b)inti,j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;voidLCS(inti,intj,char*x,int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);printf(%c,xi);else
3、if(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);constintM=7;constintN=6;voidoutput(char*s,intn);voidLCSLength(intm,intn,char*x,char*y,int*c,int*b);voidLCS(inti,intj,char*x,int*b);voidmain()/X=A,B,C,B,D,B,C/Y=B,D,C,D,B,Acharx=,A,B,C,B,D,B,C;chary=,B,D,C,D,B,A;int*c=newint*M+1;int*b=newint*M+1;for(inti=0;i
4、=M;i+)ci=newintN+1;bi=newintN+1;coutvv序列X:vvendl;output(x,M);coutvv序列Y:vvendl;output(y,N);LCSLength(M,N,x,y,c,b);coutvv序列X、Y最长公共子序列长度为:vvcMNvvendl;coutvv序列X、Y最长公共子序列为:vvendl;LCS(M,N,x,b);coutvvendl;voidoutput(char*s,intn)for(inti=1;i=n;i+)coutsi;coutendl;四、运行结果rICAUsersAdministrato叭D-eektopDebug长公共子
5、序?!1.为既.?IJ列子子共共C公公BfitDB曰IXccxX厠B別D別列rA序IB1-IO:BCDBPressanykeytocontinuerrr卜分析:在算法LCSLength中,由于每个数组单元的计算耗时0(1)时间,所以,算法LCSLength耗时O(m+n)。在算法LCS中,每一次递归调用使i或j减1,因此算法的计算时间为0(m+n)。在算法LCSLength和LCS中,可以将数组b省去,因为,数组元素cij的值仅由ci-1j-1,ci-1j和cij-1这三个数组元素的值所确定。对于给定的数组元素cij,可以不借助于数组b而仅借助与数组c本身在0(1)时间内确定cij的值。基本题
6、二:最大字段和问题一、实验目的与要求1、熟悉最长最大字段和问题的算法;2、进一步掌握动态规划算法;二、实验题若给定n个整数组成的序列a,,a2,a3,a,求该序列形如a.+a.,.+a的最大123nii1n值。三、程序代码#include#defineNUM1001intaNUM;intMaxSum(intn,int*a,int&besti,int&bestj)intsum=0;for(inti=1;i=n;i+)intthissum=0;for(intj=i;jsum)sum=thissum;besti=i;bestj=j;returnsum;voidmain()intn;intbesti,
7、bestj;coutvv请输入数组的长度:vvendl;cinn;while(true)besti=0;bestj=0;coutvv请输入数组的内容,以空格隔开:vvendl;for(inti=1;iv=n;i+)cinai;coutvv最大子段和为:vvMaxSum(n,a,besti,bestj)vvendl;coutvv最大子段和的序列是从vvbestivv到vvbestjvvendl;break;四、运行结果分析:本算法的计算时间为0(2)。针对最大子段和这个具体问题本身的结构,还可以从算法设计的策略上对上述0(2)计算时间算法加以更深刻的改进。从问题的解的结构看出,可以用分治法求解。
8、提高题一:用动态规划法求解0/1背包问题一、实验要求与目的1、掌握动态规划算法求解问题的一般特征和步骤。2、使用动态规划法编程,求解0/1背包问题。二、实验内容1、问题描述:给定n种物品和一个背包,物品i的重量是W.,其价值为V,问如何选择装ii入背包的物品,使得装入背包的物品的总价值最大?2、程序代码#includeusingnamespacestd;typedeffloatType;templatevoidKnapsack(Typev,intw,intc,intn,Type*m)intjMax=min(wn-1,c)for(intj=0;j=jMax;j+)mnj=0;for(intj=w
9、n;j1;i-)jMax=min(wi-1,c);for(intj=0;j=jMax;j+)mij=mi+1j;for(intj=wi;j=w1)m1c=max(m1c,m2c-w1+v1);templatevoidTraceback(Type*m,intw,intc,intn,intx)for(inti=1;ic;coutvv输入物品数:vvendl;cinn;coutvv请分别输入物品的重量:vvendl;for(i=0;ivn;i+)cinwi;coutvv请分别输入物品的价值:vvendl;for(i=0;ivn;i+)cinvi;maxV=Knapsack(v,w,c,n,m);coutvv最大物品的价值为:vvendl;3、程序实现;给出实例测试结
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 流函数-涡量表达法编程说明
- 苏少版八年级美术教案(全册)分析
- (完整版)苏教版一年级下册美术教案
- 北京师范大学333教育综合考研4套真题
- 2024早教国赛(四)专项测试卷
- 外研版七年级下册重点语法总结
- 2024届湖南省郴州市高三第二轮复习测试卷数学试题(六)
- 劳动仲裁专项督查工作方案
- 2024秋期国家开放大学专科《建设法规》一平台在线形考(形成性作业一至五)试题及答案
- 如何厘清阅读教学设计途径培养良好语篇教学意识
- 统编版语文四年级上册 第二单元 习作:我的家人 课件
- 重大事故隐患判定标准与相关事故案例培训课件
- 火龙罐综合灸疗法
- 第一讲 伟大事业都始于梦想(课件)
- (全)电梯安全风险管控清单
- 上期开特下期必开特规律
- (完整版)5以内的加减法(可直接打印)
- 指导青年教师活动记录(12篇)
- 《梁山伯与祝英台》PPT课件.ppt
- 机电控制工程基础实验报告
- 印刷企业管理五项制度
评论
0/150
提交评论