實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃算法

1、實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃算法 基本題一：最長(zhǎng)公共子序列問(wèn)題一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)公共子序列問(wèn)題的算法；2、初步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題    若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。給定2個(gè)序列X=x1,x2,xm和Y=y1,y

2、2,yn，找出X和Y的最長(zhǎng)公共子序列。 三(1)實(shí)驗(yàn)源代碼:/最長(zhǎng)公共子序問(wèn)題:/問(wèn)題描述: 若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，/是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對(duì)于所有j=1,2,k有：zj=xij。/例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。/給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。/給定2個(gè)序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長(zhǎng)公共子序列。 #include<bits/stdc+

3、.h>using namespace std;#define max 1000/注意：這里使用的char數(shù)組，可以按字符輸出，若改為string類型，/執(zhí)行printf("%c",Am-1)就會(huì)報(bào)錯(cuò); char A100,B100; /輸入的兩個(gè)串a(chǎn)和b/這里定義全局變量可以不賦值0，因?yàn)槿肿兞孔詣?dòng)賦值0; int cmaxmax; /記錄最長(zhǎng)公共子序的長(zhǎng)度； int bmaxmax; /記錄狀態(tài)號(hào); void LCS(int m,int n)if(m=0|n=0)return;else if(bmn=1)LCS(m-1,n-1);printf("%c&q

4、uot;,Am-1); else if(bmn=2)m=m-1;LCS(m,n);else if(bmn=3)n=n-1;LCS(m,n);void LCS_length(int m,int n)for(int i=1;i<=m;i+)for(int j=1;j<=n;j+)if(Ai-1=Bj-1)cij=ci-1j-1+1;bij=1;else if(ci-1j>=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;int main()printf("請(qǐng)輸入兩個(gè)待測(cè)的字符串:n");scanf("%s"

5、;,&A); scanf("%s",&B);int m=strlen(A); /m為A串長(zhǎng)度； int n=strlen(B); /n為B串長(zhǎng)度; LCS_length(m,n);printf("其最長(zhǎng)公共子序的長(zhǎng)度為:%dn",cmn);printf("其最長(zhǎng)公共子序?yàn)?");LCS(m,n);return 0;(2)運(yùn)行結(jié)果為:(3)算法思路:最長(zhǎng)公共子序列的結(jié)構(gòu)有如下表示：設(shè)序列X=<x1, x2, , xm>和Y=<y1, y2, , yn>的一個(gè)最長(zhǎng)公共子序列Z=<z1, z2,

6、 , zk>，則：1. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；2. 若xmyn且zkxm ，則Z是Xm-1和Y的最長(zhǎng)公共子序列；3. 若xmyn且zkyn ，則Z是X和Yn-1的最長(zhǎng)公共子序列。其中Xm-1=<x1, x2, , xm-1>，Yn-1=<y1, y2, , yn-1>，Zk-1=<z1, z2, , zk-1>?；绢}二：最大字段和問(wèn)題 一、實(shí)驗(yàn)?zāi)康呐c要求1、熟悉最長(zhǎng)最大字段和問(wèn)題的算法；2、進(jìn)一步掌握動(dòng)態(tài)規(guī)劃算法；二、實(shí)驗(yàn)題若給定n個(gè)整數(shù)組成的序列a1，a2，a3，an，求

7、該序列形如aiai1an的最大值。三，實(shí)驗(yàn)源代碼:#include<bits/stdc+.h>#define max 1000using namespace std;int N; /表示一個(gè)數(shù)組的長(zhǎng)度值;int dpmax; /記錄以i為結(jié)尾的最大子段和; /通過(guò)dp數(shù)組記錄最優(yōu)下標(biāo)的start和end; void Maxsum(int a)int maxx=0;int end,start;for(int i=1;i<=N;i+)if(dpi-1>0)dpi=dpi-1+ai;elsedpi=ai;if(maxx<=dpi)maxx=dpi;end=i;start

8、=end;int i;for(i=start-1;i>=0;i-)if(dpi>=0)start=i;elsebreak;i+;start=i;printf("MaxSum:%dn",dpend);printf("Best start:%dn",start);printf("Best end:%dn",end);int main()printf("請(qǐng)輸入一組數(shù)據(jù)的元素個(gè)數(shù):");scanf("%d",&N);int *a=new int N+1;printf("請(qǐng)輸

9、入元素的值:");for(int i=1;i<=N;i+)scanf("%d",&ai);Maxsum(a);delete a;return 0;（2）運(yùn)行結(jié)果:(3)算法思路:其實(shí)，我們?cè)谶x擇一個(gè)元素aj的時(shí)候，只有兩種情況，將ai至aj-1加上，或者從aj以j為起點(diǎn)開(kāi)始。我們用一個(gè)數(shù)組dpi表示以i為結(jié)束的最大子段和，對(duì)于每一個(gè)ai，加上dpi-1成為子段，或以ai開(kāi)始成為新段的起點(diǎn)。因?yàn)槲覀冎恍枰涗沝p值，所以復(fù)雜度是O(n)。 這就是最大子段和的動(dòng)態(tài)規(guī)劃算法。 我們甚至不需要dp數(shù)組，只需要定義一個(gè)dp變量，因?yàn)樽詈笠?/p>

10、的dp值也是最大的，所以我們可以在求dp的時(shí)候更新為最大的。提高題一： 用動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題一、實(shí)驗(yàn)要求與目的1、 掌握動(dòng)態(tài)規(guī)劃算法求解問(wèn)題的一般特征和步驟。2、 使用動(dòng)態(tài)規(guī)劃法編程，求解0/1背包問(wèn)題。二、實(shí)驗(yàn)內(nèi)容1、 問(wèn)題描述：給定n種物品和一個(gè)背包，物品i的重量是Wi，其價(jià)值為Vi，問(wèn)如何選擇裝入背包的物品，使得裝入背包的物品的總價(jià)值最大？2、 算法描述。3、 程序?qū)崿F(xiàn)；給出實(shí)例測(cè)試結(jié)果。三.(1)實(shí)驗(yàn)源代碼:/用動(dòng)態(tài)規(guī)劃的方法求解0/1背包問(wèn)題/要求:/input:n 表示總共有n種物品/ W 表示每種物品的重量/ V 表示每種物品的價(jià)值/ c 表示背包的容量 #includ

11、e<bits/stdc+.h>using namespace std;int n,c;int dp10051005;void Knapsack(int V,int W,int c,int n,int dp1005)int i,j;int jMax=min(Wn-1,c); /這里必須是Wn-1,否則，在Wn-1時(shí)刻也是合法情況; for(j=0;j<=jMax;j+)dpnj=0; /i=n,j<wn;for(j=Wn;j<=c;j+)dpnj=Vn;for(i=n-1;i>1;i-)jMax=min(Wi-1,c);for(j=0;j<=jMax;j

12、+)dpij=dpi+1j; /若小于當(dāng)前的背包容量，則不裝入; for(j=Wi;j<=c;j+)dpij=max(dpi+1j,dpi+1j-Wi+Vi); /比較裝入的代價(jià)，謀求最大代價(jià); dp1c=dp2c;if(c>=W1)dp1c=max(dp1c,dp2c-W1+V1);void Traceback(int dp1005,int W,int c,int n,int x)/x數(shù)組用來(lái)存放是否第i個(gè)元素被裝栽進(jìn)來(lái)for(int i=1;i<n;i+)if(dpic=dpi+1c)xi=0;elsexi=1;c=c-Wi; xn=(dpnc)?1:0;for(int

13、i=1;i<=n;i+)if(xi=1)printf("第%d個(gè)物品裝入n",i);int main()printf("請(qǐng)輸入物品的數(shù)量和背包的容量:");scanf("%d %d",&n,&c);int *W=new int n;int *V=new int n;int *x=new int n;W0=0,V0=0,x0=0;printf("請(qǐng)輸入每個(gè)物品的重量:n");for(int i=1;i<=n;i+)scanf("%d",&Wi);printf(&

14、quot;請(qǐng)輸入每個(gè)物品的價(jià)值:n"); for(int i=1;i<=n;i+)scanf("%d",&Vi);Knapsack(V,W,c,n,dp);Traceback(dp,W,c,n,x);return 0;(2)運(yùn)行結(jié)果:(3)算法思路：令V(i,j)表示在前i(1<=i<=n)個(gè)物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品的最大價(jià)值，則可以得到如下的動(dòng)態(tài)規(guī)劃函數(shù):(1)   V(i,0)=V(0,j)=0 (2)   V(i,j)=V(i-1,j)  j<wi         V(i,j)=maxV(i-1,j) ,V(i-1,j-wi)+vi) j>wi(1)式表明：如果第i個(gè)物品的重量大于背包的容量，則裝人前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到