资源描述
实验二、动态规划算法的应用班级：计072学号：3070911052姓名：赵凯一、实验目的与实验内容1、掌握动态规划算法的基本设计思想与原则。2、最长公共子序列、0-1背包，找零钱二、实验要求1用C+/C完成算法设计和程序设计并上机调试通过。2撰写实验报告，提供实验结果和数据。3分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。三、程序实现最长公共子序列：对字符串X和Y，首先构建子问题最有值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中Xi=x1,x2,xi;Yj=y1,y2,yj.当i=0或j=0时，空序列就是Xi和Yj的最长公共子序列。故此时cij=0.其他情况下，由最优子结构性质可建立递归关系如下：0 i=0,j=0cij=ci-1j-1+1 i,j0;xi=yjmaxcij-1,ci-1j i,j0;xi=yj0-1背包问题：设所给0-1背包问题的子问题 maxnk=ivkxknk=ivkxk=jxk0.1,i=k=wim(i+1,j) 0=j=wnm(n,j)=0 0=jwn找零钱：在这次实验中，由于听错实验的最后一个题目，所以找零钱的这个实验我是完全参照0-1背包问题的。时间复杂度：最长公共子序列：计算最优值cij的算法设计中，双层循环外规模为m，内规模为n，所以计算它的时间复杂度为0(mn).0-1背包与找零钱：由他的递归表达式可得时间复杂度为0(nc).四、心得体会通过此次实验，我的最深感触就是对算法的思想一定要理解，不然只是徒劳。刚开始做实验时，我什么也没看，直接拿着题目就凝思苦想，然而没有头绪。在把课本上的东西看了之后，通过仔细查看动态规划的思想，我明白了如何规划问题，如何解决问题。关键还是要做到心里有底，然后才能胸有成竹， 五、源程序清单。最长公共子序列：#includeusing namespace std;void LCSLength(int m,int n,char x,char y,int c8,int b8)/求最优值int i,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;else cij=cij-1;bij=3;void LCS(int i,int j,char x,int b8)/求最优解if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;else if(bij=2)LCS(i-1,j,x,b);else LCS(i,j-1,x,b);int main()char x8;char y7;int c88=0;int b88=0; coutinput string xendl;/输入字符串xfor(int i=0;ixi;coutendl;coutinput string yendl;/输入字符串yfor(int j=0;jyj;coutendl;LCSLength(7,6,x,y,c,b);coutthe best value:endl;for( i=0;i=7;i+) for(int j=0;j=6;j+)coutcij;coutendl; cout最长公共子序列:endl;LCS(7,6,x,b);coutendl;return 0;0-1背包问题：#includeusing namespace std;void tback(int m11,int t,int c,int n,int x);void knapsack(int v,int w,int c, int n,int m11)/最优值的求解过程int jmax=(wn-1)c?c:(wn-1);for(int j=0;j=jmax;j+)mnj=0;for(j=wn;j=0;i-)jmax=(wi-1c)?c:(wi-1); for(j=0;j=jmax;j+)mij=mi+1j; for(j=wi;j(mi+1j-wi+vi)?mi+1j:(mi+1j-wi+vi); m1c=m2c; if(c=w1)m1c=m1c(m2c-w1+v1)?m1c:(m2c-w1+v1);int main()int i,j,n=5,c,x6,count=0;int v6;int w6;coutinput arry v:;for(i=0;ivi;coutarry v is :endl;for(i=0;i6;i+)coutviendl;coutinput arry w:;for(i=0;iwi;coutarry w is :endl;for(i=0;i6;i+)coutwiendl;int m711=0;coutinput volum:c;knapsack(v,w,c,n,m);for(i=1;i=n;i+)for(j=1;j=c;j+) coutmij ;coutendl;tback(m,w,c,n,x);coutthe result is:;for(i=0;in;i+)if(xi)coutwi ; count+;coutendl;coutlatest number=count;return 0;void tback(int m11,int w,int c,int n,int x)/最优解得求解过程for(int i=0;in;i+)if(mic=mi+1c)xi=0; else xi=1; c-=wi; xn=(mnc)?1:0;找零钱：#includeusing namespace std;void tback(int m11,int t,int c,int n,int x);void knapsack(int v,int w,int c, int n,int m11)/最优值int u=(wn-1)c?c:(wn-1);for(int j=0;j=u;j+)mnj=0;for(j=wn;j=0;i-)u=(wi-1c)?c:(wi-1); for(j=0;j=u;j+)mij=mi+1j; for(j=wi;j(mi+1j-wi+vi)?mi+1j:(mi+1j-wi+vi); m1c=m2c; if(c=w1)m1c=m1c(m2c-w1+v1)?m1c:(m2c-w1+v1);int main()int i,j,n,c,x6=0,count=0;int t6;int co6;coutinput the value of the coin :;/输入硬币的面值for(i=0;iti;cout every coin value is :endl;for(i=0;i6;i+)couttiendl;coutinput number of every coin:;/输入对应面值硬币的个数for(i=0;icoi;coutthe number of every coin is :endl;for(i=0;i6;i+)coutcoiendl;int m711=0;n=5;coutc;knapsack(co,t,c,n,m);for(i=1;i=n;i+)for(j=1;j=c;j+) coutmij ;coutendl;tback(m,t,c,n,x);coutthe result is:;for(i=0;in;i+)if(xi)coutti ; count+;coutendl;coutlatest number=count;return 0;void tback(int m11,int t,int c,int n,int x)/最优解for(int i=0;in;i+)if(mic=mi+1c)xi=0; else xi=1; c-=ti; xn=(mnc)?1:0;
展开阅读全文