用动态规划法解决最长公共子序列问题

1、用动态规划法解决最长公共子 序列问题动态规划解最长子序列一、课程设计目的掌握动态规划法的原理，并能够按其原理编 程实现求两个序列数据的最长公共子系列，以加 深对其的理解。二、课程设计内容1、用动态规划法解决最长子序列问题2、交互输入两个序列数据3、输出两个序列的最长公共子序列三、概要设计四、详细设计与实现#in elude iostream.h#in elude ioma nip.h#defi ne max 100voidLCSLe ngth(i ntm,i nt n ,char *x,char*y,char *b)int i,j,k;int cmaxmax;for(i=1;i=m;i+)ci

2、0=0；for(i=1;i=n ;i+)cOi=O；for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;k=i* (n+1)+j; bk=|; else cij=cij-1;k=i*( n+1)+j; bk=-;void LCS(int i,int j,char *x,char *b,int width) if(i=0 | j=0)return;int k=i*(width+1)+j;if(bk=W)LCS(i-1,j-1,x,b,width); coutxi 0 ; xi = yi 时,cij = ci-1j-1 + 1 当 i , j 0 ; xi != yi

3、 时,cij = max cij-1 , c i-1j #in clude#defi ne max(a,b) ab?a:b#defi ne M 100void display(i nt &n ,i nt & C,i nt wM,i nt vM) int i;coutn;cout C;coute ndl;cout请输入各物品的大小或重量w:e ndl;w0=0;for(i=1;i wi;cout请输入各物品其价值v:endl;v0=0;for(i=1;i vi;intkn apsack(i nt&n,int & C,i ntwM,i ntvM,i nt VMM)int i,j;for (i=0;

4、i=n ;i+)for(j=0;jj)V【ij=V【i-1j;else if(wi=j)V【i【j=max(Vi-1【j,V【i-1【j-wi+vi);retur n Vn 【C;；void traceback(i nt n,i nt C,i nt wM,i nt xM,i ntVMM)for( int i=1;i0)?1:0;void mai n()int i,j, n,C;char ch;int wM,vM,xM;int VMM;whiledisplay( n,C,w,v);e ndl;cout运算结果如下： for(i=1;i=n ;i+) xi=0;kn apsack( n,C,w,v,V); cout ; for(j=0;j=C;j+) coutj ;coute ndl;for(i=0;i=n ;i+)couti ;for(j=0;j=C;j+) coutVijvv;coute ndl; coute ndl;cout选择的物向量表示为cout(;traceback( n,C,w,x,V);for(i=1;i=n ;i+) coutxi;cout)e ndl;大 价 值否则按任意键cout 背 包 最 为