用動態(tài)規(guī)劃法解決最長公共子序列問題

1、動態(tài)規(guī)劃解最長子序列課程設計目的掌握動態(tài)規(guī)劃法的原理，并能夠按其原理編程實現(xiàn)求兩個序列數(shù)據(jù)的最長公共子系列，以加深對其的理解。二、課程設計內(nèi)容1、用動態(tài)規(guī)劃法解決最長子序列問題2、交互輸入兩個序列數(shù)據(jù)3、輸出兩個序列的最長公共子序列三、概要設計四、詳細設計與實現(xiàn)#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;，.最長公共子序列問題具有最優(yōu)子結構性質(zhì)設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的最長公共子序列由性質(zhì)導出子問題的遞歸結構當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'請輸入物品種數(shù)n：?請輸入背包總容量c*s請輸入各物品的大，I1或重量u：2357141請輸入各物品苴價值小1B51576183恒算結果如下;012345678?1011121314150800000孫00&00g0001D010101010101010101010101010IB2D010101015151515151515151515153Q010101015152525253030303030304D010101015152525253

6、030303032325Q610161616212531313136363636366Q610161824283434343943494949S4?Q61016192428343?37394349525254選擇的物向量表示為：11101105背包最大價值為追4按丫或少繼續(xù)操作，否則按任意鍵#include<iostream.h>#definemax(a,b)a>b?a:b#defineM100voiddisplay(int&n,int&C,intwM,intvM)inti;cout<<"請輸入物品種數(shù)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«"背包最大價值為:&