《實驗二 動態(tài)規(guī)劃算法》由會員分享，可在線閱讀，更多相關《實驗二 動態(tài)規(guī)劃算法（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、實驗二動態(tài)規(guī)劃算法 基本題一：最長公共子序列問題 一、 實驗目的與要求 1、 熟悉最長公共子序列問題的算法； 2、 初步掌握動態(tài)規(guī)劃算法； 二、 實驗題 若給定序列X=｛x1,x2，…,xm｝，則另一序列Z=｛z1,z2,…,zk｝，是X的子序列是指 存在一個嚴格遞增下標序列｛i1,i2,…,ik｝使得對于所有j=1,2,…,k有：zj=xij。例如, 序列Z=｛B，C，D，8｝是序列X=｛A，B，C，B，D，A，8｝的子序列，相應的遞增 下標序列為｛2, 3, 5, 7｝。 給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z 是序列X和Y的公共子序列。 給定

2、2個序列X=｛x1,x2,—,xm｝和 Y=｛y1,y2,…,yn｝，找出X和Y的最長公共子序列。 三?(1)實驗源代碼： 〃最長公共子序問題： 〃問題描述：若給定序列X=｛x1,x2,…,xm｝，則另一序列Z=｛z1,z2,…,zk｝， //是X的子序列是指存在一個嚴格遞增下標序列 ｛i1,i2,…,ik｝使得對于所有 j=1,2，…,k 有：zj=xij。 〃例如，序列Z=｛B，C，D，8｝是序列X=｛A，B，C，B，D，A，B｝的子序列，相 應的遞增下標序列為｛2, 3, 5, 7｝。 〃給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時，稱Z 是序列X和Y的公共

3、子序列。 〃給定2個序列X=｛x1,x2,^,xm｝和 Y=｛y1,y2,…,yn｝,找出X和Y的最長公共子序 列。 #include using namespace std; #define max 1000 〃注意：這里使用的char數(shù)組，可以按字符輸出，若改為string類型， 〃執(zhí)行 printf("%c",A[m-1])就會報錯； char A[100],B[100]; 〃輸入的兩個串a(chǎn)和b 〃這里定義全局變量可以不賦值0,因為全局變量自動賦值0; int c[max][max]; //記錄最長公共子序的長度； int b[max][

4、max]; 〃記錄狀態(tài)號； void LCS(int m,int n) ｛ if(m==0||n==0) ｛ return; } else if(b[m][n]==1) { LCS(m-1,n-1); printf("%c",A[m-1]); } else if(b[m][n]==2) { m=m-1; LCS(m,n); } else if(b[m][n]==3) { n=n-1; LCS(m,n); } } void LCS_length(int m,int n) { for(int i=1;i<=m;i++) { for(int j=

5、1;j<=n;j++) { if(A[i-1]==B[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } } int main() { printf("請輸入兩個待測的字符串:\n"); scanf("%s",&A); scanf("%s",&B); int m=strlen(A); //m 為 A

6、 串長度； int n=strlen(B); //n 為 B 串長度； LCS_length(m,n); printf("其最長公共子序的長度為:%d\n",c[m][n]); printf("其最長公共子序為:”)； LCS(m,n); return 0; } (2)運行結果為: (3)算法思路： 最長公共子序列的結構有如下表示： 設序列X=＜x1, x2，…,xm＞和 Y=＜y1, y2，…,yn＞的一個最長公共子序列 Z=VZ],名2，???,Zk＞，則： 1.若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列; 2. 若x

7、m^yn且zk^xm，則Z是Xm-1和Y的最長公共子序列; 3. 若xm凱且硬n，則Z是X和Yn-1的最長公共子序列。 其中 Xm-1=，Yn-1=，Zk-1=。 0 ifj =0or 7 = 0. c[i,j\ = 薄-\J -\]+ I if j J > 0 and Xj =為 max(c[i\ j - l]tc[i — I. J]) j > OandXf 手 yj 基本題二：最大字段和問題 一、 實驗目的與要求 1、 熟悉最長最大字段和問題的算法； 2、 進一步掌握動態(tài)規(guī)劃

8、算法； 二、 實驗題 若給定n個整數(shù)組成的序列a1, a2, a3， an，求該序列形如a.+a. ,1+ +an的最大值。 三，實驗源代碼： #include #define max 1000 using namespace std; int N; 〃表示一個數(shù)組的長度值； int dp[max]; //記錄以i為結尾的最大子段和； 〃通過dp數(shù)組記錄最優(yōu)下標的start和end; void Maxsum(int a[]) { int maxx=0; int end,start; for(int i=1;i<=N;i++) {

9、if(dp[i-1]>0) { dp[i]=dp[i-1]+a[i]; } else dp[i]=a[i]; } if(maxx<=dp[i]) ( maxx=dp[i]; end=i; } } start=end; int i; for(i=start-1;i>=0;i--) { if(dp[i]>=0) { start=i; } else { break; } } i++; start=i; printf("MaxSum:%d\n",dp[end]); printf("Best start:%d\n",start); printf("Be

10、st end:%d\n",end); } int main() { printf("請輸入一組數(shù)據(jù)的元素個數(shù):"); scanf("%d",&N); int *a=new int [N+1]; printf("請輸入元素的值:")； for(int i=1;i<=N;i++) { scanf("%d",&a[i]); } Maxsum(a); delete a; return 0; } (2)運行結果: (3)算法思路： 其實，我們在選擇一個元素a[j]的時候，只有兩種情況，將a[i]至a[j-1]加上， 或者從a[j]以 j為起點開始。我們用一個數(shù)組

11、dp[i]表示以i為結束的最大子段和， 對于每一個3司，加上dp[i-1 ]成為子段，或以a[i]開始成為新段的起點。因為我 們只需要記錄dp值，所以復雜度是O(n)。 這就是最大子段和的動態(tài)規(guī)劃算法。 我們甚至不需要dp數(shù)組，只需要定義一個dp變量，因為最后要求的dp值也是 最大的，所以我們可以在求dp的時候更新為最大的。 提高題一：用動態(tài)規(guī)劃法求解0/1背包問題 一、 實驗要求與目的 1、 掌握動態(tài)規(guī)劃算法求解問題的一般特征和步驟。 2、 使用動態(tài)規(guī)劃法編程，求解0/1背包問題。 二、 實驗內(nèi)容 1、 問題描述：給定n種物品和一個背包，物品i的重量是可］，其價值為*問 如何

12、選擇裝入背包的物品，使得裝入背包的物品的總價值最大？ 2、 算法描述。 3、 程序實現(xiàn)；給出實例測試結果。 三.(1)實驗源代碼： 〃用動態(tài)規(guī)劃的方法求解0/1背包問題 //要求： //input:n表示總共有n種物品 // W表示每種物品的重量 // V表示每種物品的價值 // c表示背包的容量 #include using namespace std; int n,c; int dp[1005][1005]; void Knapsack(int V[],int W[],int c,int n,int dp[][1005]) {

13、int i,j; int jMax=min(W[n]-1,c); 〃這里必須是W[n]-1，否則，在W[n-1 ]時刻也是合 法情況； for(j=0;j<=jMax;j++) { dp[n][j]=0; //i=n,j1;i--) { jMax=min(W[i]-1,c); fo&ns人njMaxy-H-) dp【5lldp【+=5Mm 游？ forcFw2'A-nJnj++) <1=5|||11戛€|1>【+1】50.之+15走2+<3、、

14、壓薄>>3尤亨? 》 dpEkildpsEj 5SCXWE) dpE【cllmax(dpEEQ.ps9wE+vE)5 } } voETracebackuln dpsloosLim wFnf ckf nkf x= for=nfHl;A=i++) ifapmExdpu+iiE) xuils 2-se xuil* ?w【w } x【nll(dpm=，)2L? for?fH*An=+土 ifxuunl) p=.n5.B￥d->售即淋

15、 } int main() { printf("請輸入物品的數(shù)量和背包的容量:"); scanf("%d %d",&n,&c); int *W=new int [n]; int *V=new int [n]; int *x=new int [n]; W[0]=0,V[0]=0,x[0]=0; printf("請輸入每個物品的重量:\n"); for(int i=1;i<=n;i++) { scanf("%d",&W[i]); } printf("請輸入每個物品的價值:\n"); for(int i=1;i<=n;i

16、++) { scanf("%d",&V[i]); } Knapsack(V,W,c,n,dp); Traceback(dp,W,c,n,x); return 0; } (2)運行結果： (3)算法思路： 令V(i,j)表示在前i(1< = i< = n)個物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品 的最大價值，則可以得到如下的動態(tài)規(guī)劃函數(shù)： (1) V(i,0)=V(0,j) = 0 (2) V(i,j)=V(i-1,j) jwi (1)式表明：如果第i個物品的重量大于背包的容量，則裝人前i個物品得到的最大價值和 裝入前i-1個物品得到的最大價是相同的，即物品i不能裝入背包；第(2)個式子表明:如果 第i個物品的重量小于背包的容量，則會有一下兩種情況：(a)如果把第i個物品裝入背包， 則背包物品的價值等于第i-1個物品裝入容量位j-wi的背包中的價值加上第i個物品的價值 vi; (b)如果第i個物品沒有裝入背包，則背包中物品價值就等于把前i-1個物品裝入容量為 j的背包中所取得的價值。顯然，取二者中價值最大的作為把前i個物品裝入容量為j的背 包中的最優(yōu)解。