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

1、动态规划解最长子序列课程设计目的掌握动态规划法的原理，并能够按其原理编程实现求两个序列数据的最长公共子系列，以加深对其的理解。二、课程设计内容1、用动态规划法解决最长子序列问题2、交互输入两个序列数据3、输出两个序列的最长公共子序列三、概要设计四、详细设计与实现#include"iostream.h"#include"iomanip.h"#definemax100voidLCSLength(intm,intn,char*x,char*y,char*b)inti,j,k；intcmaxmax;for(i=1;i<=m;i+)ci0=0；for(i=1

2、;i<=n;i+)c0i=0；for(i=1;i<=m;i+)for(j=1;j<=n;j+)if(xi-1=yj-1)cij=ci-1j-1+1;k=i*(n+1)+j;bk=''elseif(ci-1j>=cij-1)，cij=ci-1j；k=i*(n+1)+j;bk='|'；elsecij=cij-1；k=i*(n+1)+j;bk尸-'voidLCS(inti,intj,char*x,char*b,intwidth)if(i=0|j=0)return;intk=i*(width+1)+j;if(bk='')L

3、CS(i-1,j-1,x,b,width);cout<<xi<<endl;elseif(bk='|')LCS(i-1,j,x,b,width);elseLCS(i,j-1,x,b,width);voidmain()charxmax='a','b','c','b','d','a','b'charymax='b','d','c','a','b','a'i

4、ntm=7;intn=6;charbmax=0;LCSLength(m,n,x,y,b);LCS(m,n,x,b,n);cout<<endl<<endl;，.最长公共子序列问题具有最优子结构性质设X=x1，xmY=y1，yn及它们的最长子序列Z=z1，zk则1、若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列2、若xm!=yn,且zk!=xm,则Z是Xm-1和Y的最长公共子序列3、若xm!=yn,且zk!=yn,则Z是Yn-1和X的最长公共子序列由性质导出子问题的递归结构当i=0,j=0时，cij=0当i,j>0;xi=yi时，ci

5、j=ci-1j-1+1当i,j>0;xi!=yi时，cij=maxcij-1,ci-1j，-同TT*F:DebugCppl.exe'请输入物品种数n：?请输入背包总容量c*s请输入各物品的大，I1或重量u：2357141请输入各物品苴价值小1B51576183恒算结果如下;012345678?1011121314150800000孙00&00g0001D010101010101010101010101010IB2D010101015151515151515151515153Q010101015152525253030303030304D010101015152525253

6、030303032325Q610161616212531313136363636366Q610161824283434343943494949S4?Q61016192428343?37394349525254选择的物向量表示为：11101105背包最大价值为追4按丫或少继续操作，否则按任意键#include<iostream.h>#definemax(a,b)a>b?a:b#defineM100voiddisplay(int&n,int&C,intwM,intvM)inti;cout<<"请输入物品种数n:"cin>>

7、;n;cout<<endl;cout<<”请输入背包总容量C:"cin>>C;cout<<endl;cout<<"请输入各物品的大小或重量w:"<<endl;w0=0;for(i=1;i<=n;i+)cin>>wi;cout<<"请输入各物品其价值v:"<<endl;v0=0;for(i=1;i<=n;i+)cin>>vi;；intknapsack(int&n,int&C,intwM,intvM,i

8、ntVMM)inti,j；for(i=0;i<=n;i+)for(j=0;j<=C;j+)if(i=0|j=0)Vi朋=0；elseif(wi>j)Vij=Vi-1j；elseif(wi<=j)Vij=max(Vi-1j,Vi-1j-wi+vi);returnVnC;；voidtraceback(intn,intC,intwM,intxM,intVMM)for(inti=1;i<=n;i+)if(ViC=Vi-1C)xi=0;elsexi=1;C=C-wi;/xn=(VnC>0)?1:0;voidmain()inti,j,n,C;charch;intwM,v

9、M,xM;intVMM;while(1)display(n,C,w,v);cout<<"运算结果如下："«endl;for(i=1;i<=n;i+)xi=O;knapsack(n,C,w,v,V);cout«"for(j=0;j<=C;j+)cout«j«"cout«endl;for(i=0;i<=n;i+)(cout«i«"for(j=0;j<=C;j+)(cout«Vij«")cout«endl;cout«endl;cout<<"选择的物向量表示为:"cout«"(traceback(n,C,w,x,V);for(i=1;i<=n;i+)cout«xi«"cout«")"«endl;cout«"背包最大价值为:&