實驗二：動態(tài)規(guī)劃

1、實驗二：動態(tài)規(guī)劃實驗?zāi)康模豪斫鈩討B(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和 子問題的重疊性質(zhì)。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的 一般方法，對較簡單的問題能正確分析，設(shè)計出動態(tài)規(guī)劃算法，并能快速編程實現(xiàn)。實驗內(nèi)容：編程實現(xiàn)講過的例題：最長公共子序列問題、滑雪問題、投資問題等。最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定 序列X=，則另一序列Z=是X的子序列是指存在一個嚴(yán)格遞增 的下標(biāo)序列 ，使得對于所有戶1,2,.,k有解答如下：a)最長公共子序列的結(jié)構(gòu)若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。易證最長公共

2、子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列 X= 和 Y=的一個最長公共子序列 Z=，則：若xm=yn，則zk=xm=yn且Zk1是Xm1和Yn1的最長公共子序列；若x：受且z蘆xm %Z是Xm 1和Y的最長公共子序列；若x：手y；且zky：，則Z是X和Yn-1的最長公共子序列。其中 Xm-1=， Yn- 1=， Zk - 1=。最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。程序如下：#include#includeint lcs_length(char x, char y);int main()char x100,y100;int len;while(1)scanf(%s%s,x,y);if(x0=0)約定

3、第一個字符串以0開始表示結(jié)束break;len=lcs_length(x,y);printf(%dn,len);int lcs_length(char x, char y)int m,n,i,j,l100100;m=strlen(x);n=strlen(y);for(i=0;im+1;i+)li0=0;for(j=0;jn+1;j+)l0j=0;for(i=1;i=m;i+)for(j=1;jli-1j)lij=lij-1;elselij=li-1j;return lmn;防衛(wèi)導(dǎo)彈一種新型的防衛(wèi)導(dǎo)彈可截?fù)舳鄠€攻擊導(dǎo)彈。它可以向前飛行，也可以用很快的速度向下 飛行，可以毫無損傷地截?fù)暨M(jìn)攻導(dǎo)彈，但

4、不可以向后或向上飛行。但有一個缺點(diǎn)，盡管它發(fā) 射時可以達(dá)到任意高度，但它只能截?fù)舯人洗谓負(fù)魧?dǎo)彈時所處高度低或者高度相同的導(dǎo) 彈?，F(xiàn)對這種新型防衛(wèi)導(dǎo)彈進(jìn)行測試，在每一次測試中，發(fā)射一系列的測試導(dǎo)彈(這些導(dǎo)彈 發(fā)射的間隔時間固定，飛行速度相同)，該防衛(wèi)導(dǎo)彈所能獲得的信息包括各進(jìn)攻導(dǎo)彈的高度， 以及它們發(fā)射次序?，F(xiàn)要求編一程序，求在每次測試中，該防衛(wèi)導(dǎo)彈最多能截?fù)舻倪M(jìn)攻導(dǎo)彈 數(shù)量，一個導(dǎo)彈能被截?fù)魬?yīng)滿足下列兩個條件之一：它是該次測試中第一個被防衛(wèi)導(dǎo)彈截?fù)舻膶?dǎo)彈；它是在上一次被截?fù)魧?dǎo)彈的發(fā)射后發(fā)射，且高度不大于上一次被截?fù)魧?dǎo)彈的高度的導(dǎo) 彈。輸入數(shù)據(jù)：第一行是一個整數(shù)n，以后的n各有一個整數(shù)表示導(dǎo)彈

5、的高度。輸出數(shù)據(jù)：截?fù)魧?dǎo)彈的最大數(shù)目。分析：定義li為選擇截?fù)舻趇個導(dǎo)彈，從這個導(dǎo)彈開始最多能截?fù)舻膶?dǎo)彈數(shù)目。由于選擇了第i枚導(dǎo)彈，所以下一個要截?fù)舻膶?dǎo)彈j的高度要小于等于它的高度，所以 li應(yīng)該等于從i+1到n的每一個j，滿足hj=hi的j中l(wèi)j的最大值。程序如下：#includeint main()int i,j,n,max,h100,l100;scanf(%d”,&n);for(i=0;i=0;i-)max=0;for(j=i+1;jhj-1&maxlj)max=lj;li=max+1;printf(%d,l0);滑雪問題滑雪問題描述：Michael喜歡滑雪百這并不奇怪，因為滑雪的確很刺

6、激。可是為了獲得速度， 滑的區(qū)域必須向下傾斜，而且當(dāng)你滑到坡底，你不得不再次走上坡或者等待升降 機(jī)來載你。Michael想知道載一個區(qū)域中最長底滑坡。區(qū)域由一個二維數(shù)組給出。 數(shù)組的每個數(shù)字代表點(diǎn)的高度。下面是一個例子 TOC o 1-5 h z 12345161718196152425207142322218131211109一個人可以從某個點(diǎn)滑向上下左右相鄰四個點(diǎn)之一，當(dāng)且僅當(dāng)高度減小。在 上面的例子中，一條可滑行的滑坡為24-17-16-1。當(dāng)然25-24-23-.-3-2-1更長。 事實上，這是最長的一條。Input輸入的第一行表示區(qū)域的行數(shù)R和列數(shù)C(1 = R,C = 100)。下

7、面是R行， 每行有C個整數(shù)，代表高度h，0=h=10000。Output輸出最長區(qū)域的長度。分析1、optxy = Max(optx-1y, optx+1y, optxy-1，optxy+1)2、在該點(diǎn)周圍的點(diǎn)中，只要其比該點(diǎn)更低，則該點(diǎn)所能滑的最長距 離等于該點(diǎn)周圍中能得最長距離加1，遞歸地執(zhí)行這個操作，直至遍歷 每個點(diǎn)。然后找也能滑得的最長距離即為所求。3、因為有備忘錄，每個點(diǎn)所能滑的最長距離只求一次，算法復(fù)雜席為O (n)#include using namespace std;int matrix100100;int cnt100100;int row ,col;int DP(int

8、i, int j)int max = 0;if (cntij-1 0)return cntij-1;if (j-1 = 0)if (matrixij matrixij-1)if (max DP(i, j-1)max = DP(i, j-1);if (j+1 matrixij+1)if (max = 0)if (matrixij matrixi-1j) if (max DP(i-1, j)max = DP(i-1, j);if (i+1 matrixi+1j)if (max rowcol;for (i=0; i=row-1; i+)for (j=0; jmatrixij;cntij = 0;fo

9、r (i=0; i=row-1; i+)for (j=0; j=col-1; j+)DP(i, j);for (i=0; i=row-1; i+)for (j=0; j=col-1; j+)if (cnt00 cntij)cnt00 = cntij;coutcnt00endl;return 0;投資問題設(shè)有8 (萬元)的投資可分給3個項目，每個項目的利潤函數(shù)如下表(一)所示:表(一)利潤函數(shù)表x012345678G1(x)05154080909598100G2(x)0515406070737475G3(x)0426404550515253解題步驟：第1步：設(shè)項目1是可用于投資的唯一項目，把x萬

10、元投資到項目1，利潤為f(x)= G1(x)這就得到表(二)的最后一行的值，投資到項目1的最優(yōu)數(shù)量為d(x)=xx=0,18；第二步：設(shè)資金8萬元可投資到項目1和項目2。由第1步已知任意數(shù)量的資源投資到項目1所產(chǎn)生的最優(yōu)，所以下到各種和式中的最大值就是目前情況下的最大利潤：G2(0)+ (8)=0+100=100G2(2)+ (6)=15+95=110G2(4)+ f1(4)=80+60=140G2(6)+ f1(2)=73+15=88G2(8)+ f1(0)=75+0=75可見將8萬元投資于項目1和2G2(1)+ f1(7)=5+98=103 G2(3)+ f1(5)=40+90=130G2

11、(5)+ f1(3)=70+40=110G2+ f1(1)=74+5=79量分別為:，所能獲得的最大利潤f2(8)及投資到項目2的最優(yōu)數(shù)f2(8)=maxG2(z)+ f1(8-z)=140z=0,18d2(8)=4；第三步：假設(shè)以任意x(尹8)萬元投資到項目1和2,對每個x值，計算從項目1和2所產(chǎn)生 的最優(yōu)利潤，即：f2(x)=maxG2(z)+ f1(x-z)z=0,1 x;投資到項目2的數(shù)量為d2(x)=產(chǎn)生 f2(x)的 z 值。得到所表(二)的結(jié)果。第四步：將8萬元投資于3個項目G3(0)+ f2(8)=0+140=140G3(2)+ f2(6)=26+96=126G3(4)+ f2(4)=45+80=125G (6)+ f (2)=51+15=66G (8)+ f(0)=53+0=53這就是原問題。則f3(8)應(yīng)取下述各量的最大值:G3(1)+ f2( 7)=4+120=124G3(3)+ f2(5)=40+90=130G3(5)+ f2(3)=50+40=90G3(7)+ f2(1)=52+5=57因此將8萬元以最優(yōu)方式投資到3個項目時所獲得的最大利潤及投資到項目3的 分別為：f3(8) =G3(0)+ f2(8)=140d3(8)=0；表