動態(tài)規(guī)劃算法章試驗報告

1、實驗報告實驗目的：理解動態(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結構性質 和子問題的重疊性質。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析 問題的一般方法，對較簡單的問題能正確分析，設計出動態(tài)規(guī)劃算法，并能快 速編程實現。實驗內容：編程實現講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三 角剖分問題、電路布線問題等。本實驗中的問題，設計出算法并編程實現。實驗過程：1. 最長公共子序列問題1.1問題描述若給定序列X=<Xi, X2,Xm>，則另一序列Z=< Zi , Z2,Zk>是X的子序列是指存在一一 個嚴格遞增的下標序列<ii, i

2、2,ik>,使得對于所有j=1,2,k有即求它們的公共子序列。1.2算法分析設序列X=<x1, x2,xm>和Y=<y1, y2,yn>的一個最長公共子序列Z=<z1, z2, -zk>，則：i. 若Xm=yn,則Zk=Xm=yn且Zk-1是Xm-1和Y n-1的最長公共子序列；ii. 若XmMy且Zkxn，則Z是X m-1和丫的最長公共子序列；iii. 若XmMy且ZkMy，則Z是X和Yn-1的最長公共子序列。其中 Xm-仁<x1, x2, ,xm1>, Yn-仁<y1, y2, ,yn1> , Zk-仁<z1, z2,

3、zkl>。最長公共子序列問題具有最優(yōu)子結構性質。用ci,j記錄序列Xi和Yj的最長公共子序列的長度。其中 Xi=<x1, x2,xi> Yj=<y1, y2,yj>。當i=0或j=0時，空序列是 Xi和Yj的最長公共子序列，故 ci,j=0。建立遞歸 關系如下：'0當i=0或j =0時ci,j=t ci -1, j -1 +1當i, j >0且Xj=yj時max® , j -1, ci -1, j p 當 i, j > 0且Xj 芒 yj時1.3程序框圖1.4程序源代碼#in clude<stdio.h>#i nclude

4、<stri ng.h>in t lcs_le ngth(char x, char y); int mai n()char x100,y100;int len ,i, n;sea nf("%d",&n);for(i=0;i< n;i+)scan f("%s%s",x,y);len=lcs_le ngth(x,y);prin tf("%dn",le n);in t lcs_le ngth(char x, char y) _int m,n ,i,j,l100100;m=strle n(x);n=strle n(y)

5、;for(i=0;i<m+1;i+)li0=0;for(j=0;j< n+1;j+)l0j=0;for(i=1;i<=m;i+)for(j=1;j<=n ;j+)if(xi-1=yj-1)i,j從1開始，但字符串是從 0開始lij=li-1j-1+1;else if(lij-1>li-1j)lij=lij-1;elselij=li-1j;return lm n;2. 矩陣連乘積問題2.1問題描述矩陣A和B可乘的條件是矩陣 A的列數等于矩陣 B的行數。若A是一個p利的矩陣，B是一個qM的矩陣，則其乘積 C=AB是一個p>f的矩陣。由該公式知計算 C=AB總共需

6、要pqr次的數乘。其標準計算公式為：%二£張覘其中1引Sp,若給定n個矩陣A1,A2,An。其中Ai與Ai+1是可乘的，i=1,2,n1。要求計算出這 n 個矩陣的連乘積 A1A2-An。使得數乘的次數最少。2.2算法思想應用動態(tài)規(guī)劃，得到'0i = j遞歸公式：mij=.r r ir i i + ri +dir i +i -MJ minmik+mk+1j + pi_4PkPj i v ji空叮2.3程序框圖2.4程序源代碼#i nclude<stdio.h>int N; void main()in t p1O1,i,j,k,r,t,v, n; int m1011

7、01;/int s101101;/sca nf("%d",&N); for(v=0;v<N;v+) scan f("%d",&n);為了跟講解時保持一致數組從1開始 記錄從第i到第j個矩陣連乘的斷開位置for(i=0;i<=n ;i+) sca nf("%d",&pi);/讀入pi的值（注意：p0到pn共n+1 項)初始化mii=0為i、j相差的值 為行為列for(i=1;i<=n ;i+)/mii=0;for(r=1;r <n ;r+)rfor(i=1;i <n ;i+)/ij=

8、i+r;/j給mij 賦初mij=mi+1j+pi-1*pi*pj;/ sij=i;for(k=i+1;k<j;k+) t=mik+mk+1j+pi-1*pk*pj;if(t<mij)mij=t;/mij取最小值sij=k;prin tf("%dn",m1 n);3. 田忌賽馬問題3.1問題描述田忌與齊王賽馬，雙方各有 n匹馬參賽（*=100 ）,每場比賽賭注為 1兩黃金，現已知 齊王與田忌的每匹馬的速度，并且齊王肯定是按馬的速度從快到慢出場，現要你寫一個程序幫助田忌計算他最好的結果是贏多少兩黃金（輸用負數表示）。3.2算法思想先排序，齊王的馬的速度放在數組a中

9、，田忌的馬的速度放在數組b中。本問題應用的算法是動態(tài)規(guī)劃和貪心算法相結合解決的。從兩人的最弱的馬入手：若田忌的馬快，就讓這兩匹馬比賽；若田忌的馬慢，干脆就讓他對付齊王最快的馬；若兩匹馬的速度相等，這時有兩種選擇方案，或者它倆比賽，或者對付齊王最快的馬。當 aij-1b：b j-1時當aij-1=b j-1時當 aij-1bj-1時定義子問題：l（i，j）為齊王的從第i匹馬開始的j匹馬與田忌的最快的j匹馬比賽，田忌 所獲得的最大收益。Il(i, j -1)l(i 1, j -1)則：l(i, j) =<maxl(i +1,j 1),l(i,j 1)程序具體實現時，為了適合c數據從0開始，稍

10、加變動，定義子問題： l（i , j）為齊王的從第i匹馬開始到第i + j匹馬共j+1匹馬與田忌的最快的j+1匹馬比賽，田忌所獲得的最大 收益。初始化時：li0表示齊王的第i匹馬與田忌最快的馬比賽的結果。3.3程序框圖#i nclude<stdio.h> void readdata();void ini t();int N, n,a100,b100,l100100;void main()int i,j,k;sca nf("%d",&N);測試例子得個數for(k=0;k<N;k+)readdata(); in it();for(i=n-2;i>

11、;=0;i-) for(j=1;j <n-i;j+)if(ai+j<bj) lij=lij-1+1； else if(ai+j>bj) lij=li+1j-1-1；else if(li+1j-1-1>lij-1) lij=li+1j-1-1； elselij=lij-1；prin tf("%dn",lO n-1);void readdata()int i;馬的個數：-sca nf("%d",&n);/for(i=0;i< n;i+)每只馬的速度；每只馬的速度；對輸入的馬的速度的無序序列進行排序scan f("

12、;%d",&ai);/ for(i=0;i< n;i+)scan f("%d",&bi);/int* qsort(int a100,int n)/int i,j,t;for(i=0;i< n;i+) for(j=i+1;j <n ;j+) if(ai<aj)t=ai;ai=aj;aj=t;/ for(i=0;i< n;i+)/ prin tf("%3d",ai);/ prin tf("n"); return a; void in it()int i;qsort(a, n);qsort(b ,n);for(i=0;i< n;i+)if(ai<b