算法分析与设计实验二

《算法分析与设计实验二》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二、动态规划算法的应用班级：计072学号：3070911052姓名：赵凯一、实验目的与实验内容1、掌握动态规划算法的基本设计思想与原则。2、最长公共子序列、0-1背包，找零钱二、实验要求1．用C++/C完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、程序实现最长公共子序列：对字符串X和Y，首先构建子问题最有值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子

2、序列的长度。其中Xi={x1,x2,…,xi};Yj={y1,y2,…,yj}.当i=0或j=0时，空序列就是Xi和Yj的最长公共子序列。故此时c[i][j]=0.其他情况下，由最优子结构性质可建立递归关系如下：0i=0,j=0c[i][j]=c[i-1][j-1]+1i,j>0;xi=yjmax{c[i][j-1],c[i-1][j]}i,j>0;xi=yj0-1背包问题：设所给0-1背包问题的子问题max∑nk=ivkxk∑nk=ivkxk<=jxk∈{0.1},i<=k<=n的最优值为m(i,

3、j),即m(i,j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：m(i,j)=max{m(i+1,j),m(i+1,j-wi)+vi}j>=wim(i+1,j)0<=j=wnm(n,j)=00<=j

4、内规模为n，所以计算它的时间复杂度为0(mn).0-1背包与找零钱：由他的递归表达式可得时间复杂度为0(nc).四、心得体会通过此次实验，我的最深感触就是对算法的思想一定要理解，不然只是徒劳。刚开始做实验时，我什么也没看，直接拿着题目就凝思苦想，然而没有头绪。在把课本上的东西看了之后，通过仔细查看动态规划的思想，我明白了如何规划问题，如何解决问题。关键还是要做到心里有底，然后才能胸有成竹，五、源程序清单。最长公共子序列：#includeusingnamespacestd;void

5、LCSLength(intm,intn,charx[],chary[],intc[][8],intb[][8])//求最优值{inti,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j

6、];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,charx[],intb[][8])//求最优解{if(i==0j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);cout<

7、ntb[8][8]={0};cout<<"inputstringx"<>x[i];cout<>y[j];cout<

8、)cout<usingnamespacestd;voidtback(intm[][11],intt[],intc,intn,intx[]);voidknapsack(intv[],intw[],intc,intn,intm[][11])//最优值的求解过程{intj