動(dòng)態(tài)規(guī)劃-劉宗凡

動(dòng)態(tài)規(guī)劃四會(huì)中學(xué)劉宗凡多階段決策過(guò)程最優(yōu)化問(wèn)題在現(xiàn)實(shí)生活中，有一類(lèi)活動(dòng)的過(guò)程，由于它的特殊性，可將過(guò)程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過(guò)程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴(lài)于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定以后，就組成一個(gè)決策序列，因此也就確定了整個(gè)過(guò)程的一條活動(dòng)路線(xiàn)。這種把一個(gè)問(wèn)題看做是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為多階段決策過(guò)程，這種問(wèn)題稱(chēng)為多階段決策最優(yōu)化問(wèn)題。引子：最短路徑問(wèn)題下圖給出了一個(gè)地圖，地圖中每個(gè)頂點(diǎn)代表一個(gè)城市，兩個(gè)城市間的連線(xiàn)代表道路，連線(xiàn)上的數(shù)值代表道路長(zhǎng)度?，F(xiàn)在，我們想從城市a到達(dá)城市E。怎樣走才能使得路徑最短，最短路徑的長(zhǎng)度是多少？窮舉法(回溯法)3*9*6*2=342條路徑路徑增多，將呈幾何級(jí)數(shù)增長(zhǎng)每次除了已經(jīng)訪(fǎng)問(wèn)過(guò)的城市外，其他城市都要訪(fǎng)問(wèn)，所以時(shí)間復(fù)雜度為O（n?。@是一個(gè)“指數(shù)級(jí)”的算法。在求b1到E的最短路徑的時(shí)候，先求出從C2到E的最短路徑；而在求從b2剄E的最短路徑的時(shí)候，又求了一遍從C2剄E的最短路徑。也就是說(shuō)，從C2到E的最短路徑求了兩遍。同樣可以發(fā)現(xiàn)，在求從Cl、C2剄E的最短路徑的過(guò)程中，從Dl到E的最短路徑也被求了兩遍。而在整個(gè)程序中，從Dl到E的最短路徑被求了四遍，這是多么大的一個(gè)浪費(fèi)??！如果在求解的過(guò)程中，同時(shí)將求得的最短路徑的距離“記錄在案”，以便將來(lái)隨時(shí)調(diào)用，則可以避免這種重復(fù)計(jì)算。

C1C3D1AB1B3B2D2EC22511214106104131112396581052求從A到E的最短路徑問(wèn)題，可以轉(zhuǎn)化為三個(gè)性質(zhì)完全相同，但規(guī)模較小的子問(wèn)題，即分別從B1、B2、B3到E的最短路徑問(wèn)題。記從Bi(i=1,2,3)到E的最短路徑為S(Bi)，則從A到E的最短距離S(A)可以表示為：

同樣，計(jì)算S(B1)又可以歸結(jié)為性質(zhì)完全相同，但規(guī)模更小的問(wèn)題，即分別求C1，C2，C3到E的最短路徑問(wèn)題S(Ci)(i=1,2,3)，而求S(Ci)又可以歸結(jié)為求S(D1)和S(D2)這兩個(gè)子問(wèn)題。從圖可以看出，在這個(gè)問(wèn)題中，S(D1)和S(D2)是以知的，它們分別是：S(D1)=5，S(D2)=2因而，可以從這兩個(gè)值開(kāi)始，逆向遞歸計(jì)算S(A)的值。S(C1)=8 且如果到達(dá)C1，則下一站應(yīng)到達(dá)D1；S(C2)=7 且如果到達(dá)C2，則下一站應(yīng)到達(dá)D2；S(C3)=12且如果到達(dá)C3，則下一站應(yīng)到達(dá)D2；S(B1)=20 且如果到達(dá)B1，則下一站應(yīng)到達(dá)C1；S(B2)=14 且如果到達(dá)B2，則下一站應(yīng)到達(dá)C1；S(B3)=19 且如果到達(dá)B3，則下一站應(yīng)到達(dá)C2；由此，可以計(jì)算S(A)：820052712141919C1C3D1AB1B3B2D2EC22511214106104131112396581052最后，可以得到：從A到E的最短路徑為AB2C1D1E?？梢钥吹剑陨戏椒ú粌H得到了從A到D的最短路徑，同時(shí)，也得到了從圖中任一點(diǎn)到E的最短路徑。

動(dòng)態(tài)規(guī)劃的基本特征

1、問(wèn)題具有多階段決策的特征。階段可以按時(shí)間劃分，也可以按空間劃分。2、每一階段都有相應(yīng)的“狀態(tài)”與之對(duì)應(yīng)，描述狀態(tài)的量稱(chēng)為“狀態(tài)變量”。3、每一階段都面臨一個(gè)決策，選擇不同的決策將會(huì)導(dǎo)致下一階段不同的狀態(tài)，同時(shí)，不同的決策將會(huì)導(dǎo)致這一階段不同的目標(biāo)函數(shù)值。4、每一階段的最優(yōu)解問(wèn)題可以遞歸地歸結(jié)為下一階段各個(gè)可能狀態(tài)的最優(yōu)解問(wèn)題，各子問(wèn)題與原問(wèn)題具有完全相同的結(jié)構(gòu)。能否構(gòu)造這樣的遞推歸結(jié)，是解決動(dòng)態(tài)規(guī)劃問(wèn)題的關(guān)鍵。這種遞推歸結(jié)的過(guò)程，稱(chēng)為“不變嵌入”。

動(dòng)態(tài)規(guī)劃的幾個(gè)概念:階段：據(jù)空間順序或時(shí)間順序?qū)?wèn)題的求解劃分階段。狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來(lái)刻畫(huà)。對(duì)問(wèn)題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對(duì)每個(gè)階段所做出的某種選擇性操作。狀態(tài)轉(zhuǎn)移方程：用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是：在做每一步?jīng)Q策時(shí)，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經(jīng)過(guò)篩選，以每一步都是最優(yōu)的來(lái)保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝（從搜索角度看），效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因?yàn)橛行﹩?wèn)題不符合最優(yōu)性原理。兩種算法的差別在于，貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。而動(dòng)態(tài)規(guī)劃會(huì)產(chǎn)生許多判定序列，再按最優(yōu)性原理對(duì)這些序列加以篩選，去除那些非局部最優(yōu)的子序列。程序設(shè)計(jì)的一般格式；fork←n-1downto1do{枚舉階段}fors取遍所有狀態(tài)doforu取遍所有決策do；這里是一種從目標(biāo)狀態(tài)往回推的逆序求法，適用于目標(biāo)狀態(tài)確定的問(wèn)題。而很多試題是確定了初始狀態(tài)的。當(dāng)然，對(duì)于初始狀態(tài)確定的問(wèn)題，我們也可以采用從初始狀態(tài)出發(fā)往前推的順序求法。事實(shí)上，這種方法對(duì)我們來(lái)說(shuō)要更為直觀(guān)、更易設(shè)計(jì)一些，從而更多地出現(xiàn)在我們的解題過(guò)程中。由于動(dòng)態(tài)程序設(shè)計(jì)方法的模式性比較強(qiáng)，因此應(yīng)該把主要精力放在狀態(tài)定義、階段劃分和狀態(tài)轉(zhuǎn)移方程的設(shè)計(jì)上。一旦這些問(wèn)題解決了，事情成功了一大半。適用DP求解問(wèn)題的特征1、最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2、重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問(wèn)題的解。使用動(dòng)態(tài)規(guī)劃的原則(一)最優(yōu)化原理(最優(yōu)子結(jié)構(gòu)原理):無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。可以通俗地理解為子問(wèn)題的局部最優(yōu)將導(dǎo)致整個(gè)問(wèn)題的全局最優(yōu)。在最短路徑問(wèn)題中，A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，滿(mǎn)足最優(yōu)化原理。也就是說(shuō)一個(gè)問(wèn)題的最優(yōu)解只取決于其子問(wèn)題的最優(yōu)解，非最優(yōu)解對(duì)問(wèn)題的求解沒(méi)有影響。如圖，若路線(xiàn)I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線(xiàn)J必是從B到C的最優(yōu)路線(xiàn)。這可用反證法證明：假設(shè)有另一路徑J’是B到C的最優(yōu)路徑，則A到C的路線(xiàn)取I和J’比I和J更優(yōu)，這與原命題矛盾。從而證明J必是B到C的最優(yōu)路徑。

最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問(wèn)題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。ABCIJJ’使用動(dòng)態(tài)規(guī)劃的原則(二)無(wú)后效性原則：某階段的狀態(tài)一旦確定，則此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響。也就是說(shuō)，“未來(lái)與過(guò)去無(wú)關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響過(guò)程未來(lái)的演變。具體地說(shuō)，如果一個(gè)問(wèn)題被劃分各個(gè)階段之后，階段I中的狀態(tài)只能由階段I-1中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其他狀態(tài)沒(méi)有關(guān)系，特別是與未發(fā)生的狀態(tài)沒(méi)有關(guān)系，這就是無(wú)后效性。

應(yīng)用動(dòng)態(tài)規(guī)劃要注意階段的劃分是關(guān)鍵，必須依據(jù)題意分析，尋求合理的劃分階段(子問(wèn)題)方法。而每個(gè)子問(wèn)題是一個(gè)比原問(wèn)題簡(jiǎn)單得多的優(yōu)化問(wèn)題。而且每個(gè)子問(wèn)題的求解中，均利用它的一個(gè)后部子問(wèn)題的最優(yōu)化結(jié)果，直到最后一個(gè)子問(wèn)題所得最優(yōu)解，它就是原問(wèn)題的最優(yōu)解。例1：數(shù)字三角形問(wèn)題：給定一個(gè)具有N層的數(shù)字三角形如下圖，從頂至底有多條路徑，每一步可沿左斜線(xiàn)向下或沿右斜線(xiàn)向下，路徑所經(jīng)過(guò)的數(shù)字之和為路徑得分，請(qǐng)求出最大路徑得分。

(1)1<三角形行數(shù)<100

(2)三角形中數(shù)字為1..99

如輸入：5

7

38

810

2774

45265

輸出：30738810

277445265回溯算法programsjx;

constmaxn=10;

var

a:array[1..maxn,1..maxn]ofinteger;

max:longint;

n,i,j:integer;

fname:string;inputf:text;proceduretry(x,y,dep:integer;sum:longint);

begin

if(dep=n)then

begin

ifsum>maxthen

max:=sum;

exit

end;

try(x+1,y,dep+1,sum+a[x+1,y]);

try(x+1,y+1,dep+1,sum+a[x+1,y+1]);

end;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);fori:=1tondoforj:=1toidoread(inputf,a[i,j]);max:=0;try(1,1,1,a[1,1]);writeln(max);end.由以上算法不難算出其時(shí)間復(fù)雜度為2^n，而本題N最大為100，顯然當(dāng)N比較大時(shí)是無(wú)法在規(guī)定時(shí)間內(nèi)出解的，但本題又很難找出理想的剪枝方法。問(wèn)題分析：假設(shè)從頂至數(shù)字三角形的某一未知的所有路徑中，所經(jīng)過(guò)的數(shù)字總和最大的那條路徑我們稱(chēng)之為未知的最大路徑。由于問(wèn)題規(guī)定每一步只能沿直線(xiàn)或右斜線(xiàn)向下走，若要走到某一位置，則其前一未知必為其左上方或正上方兩個(gè)位置之一。由此可知，當(dāng)前未知的最優(yōu)路徑必定與其左上方或正上方兩個(gè)位置的最優(yōu)路徑有關(guān)，且來(lái)自于其中更優(yōu)的一個(gè)。我們可以用一個(gè)二維數(shù)組maxsum記錄每個(gè)位置的最優(yōu)路徑的數(shù)字總和。計(jì)算maxsum數(shù)組可以像計(jì)算楊輝三角一樣用逐行遞推的方法實(shí)現(xiàn)。動(dòng)態(tài)轉(zhuǎn)移方程：f(i,j)=max{f(i-1,j),f(j-1,j-1)}+a[i,j]f[1,1]:=a[1,1];fori:=2tondobeginf[i,1]:=a[i,1]+f[i-1,1];forj:=2toidoiff[i-1,j-1]>f[i-1,j]

thenf[i,j]:=a[i,j]+f[i-1,j-1]elsef[i,j]:=a[i,j]+f[i-1,j];end;maxsum:=0;fori:=1tondoiff[n,i]>maxsumthenmaxsum:=f[n,i];writeln(maxsum);end.constmaxn=100;varfname:string;inputf:text;n,i,j:integer;a:array[1..maxn,1..maxn]ofinteger;f:array[1..maxn,1..maxn]ofinteger;maxsum:integer;beginreadln(n);fori:=1tondoforj:=1toidoread(inputf,a[i,j]);fillchar(f,sizeof(f),0);思考：方格取數(shù)如下圖，n*m的方格，每個(gè)方格存放了一個(gè)正整數(shù)，一個(gè)卒子從左上角走到右下角，走的過(guò)程中只能向下或向右，到達(dá)每個(gè)方格就取出該方格內(nèi)的數(shù)，走到右下角所取得數(shù)之和稱(chēng)之為效益，求效益的最大值。3898288383199809288387219123271838828263578提示：Fij=max{fi,j-1,fi-1,j}+aij,邊界條件：F1,1=a1,1answer=Fnm例2：0/1背包問(wèn)題一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價(jià)值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。輸入樣例：

11 {weight}

4 {n}

2467 {W[i]}

6101213 {P[i]}輸出樣例：

23分析最優(yōu)子結(jié)構(gòu)性質(zhì)分析：我們首先自問(wèn)一個(gè)簡(jiǎn)單的問(wèn)題：在最優(yōu)解中，是否包括了xi(I=1..n)？只可能有兩種情況： 1.包括有。那么何妨另起爐灶，換一個(gè)更簡(jiǎn)單的問(wèn)題來(lái)思考：在背包載重為m-wi的情況下，在其它n-1件物品中挑選，使得價(jià)值和最大。等把這個(gè)子問(wèn)題求出后，再加上vi的價(jià)值就是整個(gè)問(wèn)題的最優(yōu)解了。 2.沒(méi)包括。那么就當(dāng)xi根本不存在，直接解物品數(shù)量為n-1，背包載重為m的子問(wèn)題。子問(wèn)題的最優(yōu)解就是問(wèn)題的最優(yōu)解。這樣，我們就看出，無(wú)論那種情況，在問(wèn)題的最優(yōu)解中，都包含著子問(wèn)題的最優(yōu)解。分析遞歸地定義問(wèn)題的解：請(qǐng)思考本題各數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)？ 價(jià)值：一維數(shù)組v[1..n] 重量：一維數(shù)組w[1..n]因?yàn)樗髥?wèn)題是n件物品，背包限重為m，隨著問(wèn)題規(guī)模的增減，n和m都在變化，因此很自然地想到把件數(shù)和背包限重都作為自變量。定義函數(shù)f(i,j)為在1~i件物品中選若干件裝入限重為j的背包中的最大價(jià)值和。那么根據(jù)前面的討論中關(guān)于第I件物品是否裝入了背包的情況分析，我們得出關(guān)系式： 當(dāng)?shù)趇件物品要裝入背包時(shí)，f(i,j):=i-1件物品，限重為j-w[I]的最優(yōu)解+v[I],即： f(i,j):=f(i-1,j-w[i])+v[i] 當(dāng)然，第i件物品要裝入是有條件限制的，是什么？ 第i件物品重量小于等于背包限重，即w[i]<=j 當(dāng)?shù)趇件物品不裝入背包時(shí)，f(i,j):=i-1件物品，限重為m的最優(yōu)解，即： f(i,j):=f(i-1,j)分析現(xiàn)在已經(jīng)求得裝入或者不裝入第i件物品的限重為J的背包的最大價(jià)值，那么接下來(lái)應(yīng)該做什么？比較這兩種情況下誰(shuí)的價(jià)值更大，更大者為當(dāng)前問(wèn)題的最優(yōu)解。 iff(i,j)’>f(i,j)’’then f(i,j):=f(i,j)’else f(i,j):=f(i,j)’’;上述遞歸式的邊界條件是什么？我們知道f(i,j)的i和J都有一個(gè)取值范圍。1<=i<=n,0<=J<=m.邊界條件就是當(dāng)問(wèn)題規(guī)?？s小到自變量下界時(shí)的函數(shù)的取值情況。當(dāng)背包限重為0時(shí)，無(wú)法放任何物品，此時(shí)所有的f(i,0):=0(1<=I<=n).這就是邊界條件。分析根據(jù)上述遞歸式已經(jīng)可以遞歸地求出最優(yōu)解了。請(qǐng)自行編程練習(xí)。下面按自底向上的方式求解本題。在按自底向上的動(dòng)態(tài)規(guī)劃方式求解問(wèn)題時(shí)，其實(shí)主要就是做一件事： 按問(wèn)題規(guī)模從小到大地求解問(wèn)題，把每階段求得的問(wèn)題的最優(yōu)解保存在表格（數(shù)組）中，以便在下一階段求解更大的問(wèn)題時(shí)，可以直接查表引用子問(wèn)題的最優(yōu)解。首先分析階段。將n件物品放入背包，故可以把階段劃分為n個(gè)。把在前I件物品中選取物品放入背包作為第I個(gè)階段。再分析狀態(tài)。第I個(gè)階段的狀態(tài)J是對(duì)前I件物品進(jìn)行取舍后得到的背包的重量。顯然狀態(tài)J滿(mǎn)足條件0<=J<=m，即是說(shuō)狀態(tài)J的取值范圍在0到背包的最大限重之間。注意，由于物品重量均為正整數(shù)，所以狀態(tài)J是0~m之間的整數(shù)，可以進(jìn)行枚舉。分析這樣，在第I個(gè)階段就有m+1個(gè)問(wèn)題需要求解，分別是f[I,0],f[I,1],…,f[I,m]。由于前面分析可知所有的f[I,0]均為0，因此實(shí)際需要求解的是m個(gè)問(wèn)題。而這m個(gè)問(wèn)題的求解基礎(chǔ)是第I-1個(gè)階段的m個(gè)子問(wèn)題。這些子問(wèn)題的最優(yōu)解已經(jīng)先于此時(shí)求得，保存在f[I-1,1],f[I-1,2],…,f[I-1,m]中，現(xiàn)在只需要直接引用它們的值就可以了。這就是動(dòng)態(tài)規(guī)劃自底向上的體現(xiàn)。最后分析決策。前面的分析中已經(jīng)明確了決策的個(gè)數(shù)，大家說(shuō)是多少個(gè)？只有兩個(gè)：在前I件物品中，限重為J的條件下，裝入第I件物品還是不裝入第I件物品。比較這兩種情況的價(jià)值和，誰(shuí)大誰(shuí)就是最優(yōu)解。分析總結(jié)一下：階段：1~n個(gè)初始階段：f[I,0]:=0(1<=I<=n);f[0,m]:=0狀態(tài)：1~m個(gè)決策：2個(gè)?，F(xiàn)在編程沒(méi)有任何困難了吧。測(cè)試數(shù)據(jù)：

10,3

3,4

4,5

5,6這個(gè)最大價(jià)值是怎么得來(lái)的呢?從背包容量為0開(kāi)始,1號(hào)物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則里面放4.這樣,這一排背包容量為4,5,6,....10的時(shí)候，最佳方案都是放4.假如1號(hào)物品放入背包.則再看2號(hào)物品.當(dāng)背包容量為3的時(shí)候，最佳方案還是上一排的最價(jià)方案c為4.而背包容量為5的時(shí)候，則最佳方案為自己的重量5.背包容量為7的時(shí)候，很顯然是5加上一個(gè)值了。加誰(shuí)??很顯然是7-4=3的時(shí)候.上一排c3的最佳方案是4.所以?？偟淖罴逊桨甘?+4為9.這樣.一排一排推下去。最右下放的數(shù)據(jù)就是最大的價(jià)值了。(注意第3排的背包容量為7的時(shí)候,最佳方案不是本身的6.而是上一排的9.說(shuō)明這時(shí)候3號(hào)物品沒(méi)有被選.選的是1,2號(hào)物品.所以得9.)０１２３４５６７８９1011０１２３４手工驗(yàn)證f(I,j)公式的正確性０１２３４５６７８９1011０000000000000１006666666666２00661010161616161616３00661010121218182222４00661010121313192323手工驗(yàn)證f(I,j)公式的正確性分析顯然這個(gè)題可用深度優(yōu)先方法對(duì)每件物品進(jìn)行枚舉(選或不選用0,1控制).程序簡(jiǎn)單,但是當(dāng)n的值很大的時(shí)候不能滿(mǎn)足時(shí)間要求，時(shí)間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問(wèn)題分解為子問(wèn)題,使用遞歸函數(shù)即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：動(dòng)態(tài)轉(zhuǎn)移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}F[n][m]即為最優(yōu)解，邊界條件為f[0][j]＝0

，f[i][0]=0;

“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價(jià)值為f[i-1][v]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。constmaxm=200;maxn=30;

typear=array[1..maxn]ofinteger;

varm,n,j,i:integer;

c,w:ar;

f:array[0..maxn,0..maxm]ofinteger;

functionmax(x,y:integer):integer;

begin

ifx>ythenmax:=xelsemax:=y;

end;

begin

readln(m,n);

fori:=1tondo

readln(w[i],c[i]);

fori:=1tomdof(0,i):=0;

fori:=1tondof(i,0):=0;

fori:=1tondo

forj:=1tomdo

begin

ifj>=w[i]

thenf[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])

elsef[i,j]:=f[i-1,j];

end;

writeln(f[n,m]);

end.思考：完全背包問(wèn)題一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，...,Wn,每件的價(jià)值分別為C1,C2,...,Cn.若的每種物品的件數(shù)足夠多.求旅行者能獲得的最大總價(jià)值。本問(wèn)題的數(shù)學(xué)模型如下：設(shè)f(x)表示重量不超過(guò)x公斤的最大價(jià)值，則f(x）=max{f(x-w[i])+c[i]}

當(dāng)x>=w[i]1<=i<=n程序如下:（順推法）programknapsack04;

constmaxm=2000;maxn=30;

typear=array[0..maxn]ofinteger;

varm,n,j,i,t:integer;

c,w:ar;

f:array[0..maxm]ofinteger;

begin

readln(m,n);

fori:=1tondo

readln(w[i],c[i]);

f(0):=0;

fori:=1tomdo

forj:=1tondo

begin

ifi>=w[j]

thent:=f[i-w[j]]+c[j];

ift>f[i]thenf[i]:=t

end;

writeln(f[m]);

end.例3：(NOIP2007)3.守望者的逃離問(wèn)題描述】惡魔獵手尤迫安野心勃勃.他背叛了暗夜精靈，率深藏在海底的那加企圖叛變：守望者在與尤迪安的交鋒中遭遇了圍殺.被困在一個(gè)荒蕪的大島上。為了殺死守望者，尤迪安開(kāi)始對(duì)這個(gè)荒島施咒，這座島很快就會(huì)沉下去，到那時(shí)，刀上的所有人都會(huì)遇難：守望者的跑步速度，為17m/s，以這樣的速度是無(wú)法逃離荒島的。慶幸的是守望者擁有閃爍法術(shù)，可在1s內(nèi)移動(dòng)60m，不過(guò)每次使用閃爍法術(shù)都會(huì)消耗魔法值10點(diǎn)。守望者的魔法值恢復(fù)的速度為4點(diǎn)/s，只有處在原地休息狀態(tài)時(shí)才能恢復(fù)?，F(xiàn)在已知守望者的魔法初值M，他所在的初始位置與島的出口之間的距離S，島沉沒(méi)的時(shí)間T。你的任務(wù)是寫(xiě)一個(gè)程序幫助守望者計(jì)算如何在最短的時(shí)間內(nèi)逃離荒島，若不能逃出，則輸出守望者在剩下的時(shí)間內(nèi)能走的最遠(yuǎn)距離。注意:守望者跑步、閃爍或休息活動(dòng)均以秒(s)為單位。且每次活動(dòng)的持續(xù)時(shí)間為整數(shù)秒。距離的單位為米(m)。【輸入】輸入文件escape.in僅一行，包括空格隔開(kāi)的三個(gè)非負(fù)整數(shù)M，S，T?！据敵觥枯敵鑫募scape.out包含兩行:第1行為字符串"Yes"或"No"(區(qū)分大小寫(xiě))，即守望者是否能逃離荒島。第2行包含一個(gè)整數(shù)，第一行為"Yes"(區(qū)分大小寫(xiě)）時(shí)表示守望著逃離荒島的最短時(shí)間第一行為"No"(區(qū)分大小寫(xiě))時(shí)表示守望者能走的最遠(yuǎn)距離?！据斎胼敵鰳永?】【輸入輸出樣例2】【限制】30%的數(shù)據(jù)滿(mǎn)足:1<=T<=10，1<=S<=10050%的數(shù)據(jù)滿(mǎn)足:1<=T<=1000，1<=S<=10000100%的數(shù)據(jù)滿(mǎn)足:1<=T<=300000，0<=M<=10001<=S<=10^8escape.in escape.out392004No197escape.in escape.out3625510 Yes6【試題分析】(方法一：貪心)分析題意歸納出每個(gè)時(shí)間單位的三種策略

A.休息（可恢復(fù)4點(diǎn)魔法值）

B.跑步（可移動(dòng)17的距離，不恢復(fù)魔法值）

C.閃爍（可移動(dòng)60的距離，并消耗10點(diǎn)魔法值）這樣很容易聯(lián)想到一個(gè)貪心規(guī)則：

A.當(dāng)魔法值>=10肯定要用閃爍移動(dòng)。（魔法儲(chǔ)存起來(lái)做什么？現(xiàn)在不用，以后也要用的，不用是浪費(fèi)）

B.考慮魔法值<10時(shí)，是休息等待魔法恢復(fù)后使用閃爍移動(dòng)還是直接跑步的效果好。

其實(shí)很簡(jiǎn)單（假設(shè)我花5s鐘來(lái)休息，那就可以積累20點(diǎn)魔法值，也就可以使用2次閃爍，移動(dòng)距離為60*2=120，而總的時(shí)間花的是5+2=7；但如果這7s我們?nèi)脕?lái)跑步，則移動(dòng)距離為17*7=119，顯然沒(méi)有用魔法劃算。既然這樣，那就不斷用魔法吧。）

C.但其實(shí)在島快沉沒(méi)的最后階段，可能出現(xiàn)魔法恢復(fù)后的值尚不足以連續(xù)使用閃爍，而跑步實(shí)際更優(yōu)。這就是本題的一個(gè)陷阱。即便是貪心也需考慮最后的這一段，應(yīng)該跑步而不是休息并閃爍。所以單獨(dú)處理即可。

（但這樣的貪心很容易忽略邊界情況，例如假設(shè)我用完初始魔法值還剩6的魔法值，則只需再休息1s就可以使用魔法了，而不一定是7s的那種情況。）【試題分析】(方法二：動(dòng)態(tài)規(guī)劃)典型的動(dòng)態(tài)規(guī)劃。

設(shè)f[i,j]為第i秒，魔法值為j時(shí)可行的最大距離。

f[i,j]:=max{f[i-1,j]+17,f[i-1,j-10]+60,f[i-1,j+4]}(當(dāng)j≥10時(shí));

f[i,j]:=max{f[i-1,j]+17,f[i-1,j+4]}(當(dāng)j<10時(shí))

按題目所說(shuō)，最大魔法值為1000，最大時(shí)間為300000秒，那么需要1000*300000=300000000=3*10^9的數(shù)組，空間會(huì)溢出，所以使用兩個(gè)一維數(shù)組來(lái)迭代，只需2*1000的數(shù)組，但是時(shí)間復(fù)雜度為O(t*m)，有可能會(huì)超時(shí)。【試題分析】(方法三：貪心+動(dòng)態(tài)規(guī)劃)1.對(duì)于初始魔法，先采用貪心思想，將其全部用完直至魔法值不足以使用閃爍為止（即M<10）。這樣就可以將問(wèn)題規(guī)?？s小，轉(zhuǎn)化為魔法初值為m（<10），

2.用f[i,j]來(lái)表示i時(shí)間魔法值為j可以達(dá)到的最遠(yuǎn)距離。假設(shè)貪心后還剩余s的路程，而全程為ss,剩余魔法為m,剩余時(shí)間為t,則很容易根據(jù)題目信息列出方程：

f[0,m]=ss-s

f[i,j]=max{f[i-1,j-4],f[i-1,j]+17,f[i-1,j+10]+60}

(1<=i<=t)

例4：求最長(zhǎng)不下降序列問(wèn)題描述：設(shè)有一個(gè)正整數(shù)的序列：b1,b2,…bn,對(duì)于下標(biāo)i1<i2<…ih,若有bi1<bi2<…<bih，則稱(chēng)存在一個(gè)長(zhǎng)度為h的不下降序列。例如，下列數(shù) 13791638242738444921526315對(duì)于下標(biāo)i1=1,i2=4,i3=5,i4=9,i5=13,且滿(mǎn)足 13<16<38<44<63則存在長(zhǎng)度為5的不下降序列。但是，我們看到還存在其它的不下降序列。如 7<9<16<18<19<21<22<63則存在長(zhǎng)度為8的不下降序列。問(wèn)題：當(dāng)給定b1,b2,…bn后，求出最長(zhǎng)的不下降序列h及這個(gè)序列中的各個(gè)數(shù)。最長(zhǎng)不下降序列-分析動(dòng)態(tài)規(guī)劃的難點(diǎn)之一：怎樣定義問(wèn)題？你首先要能定義出問(wèn)題是什么，才能進(jìn)一步定義出子問(wèn)題是什么，然后才能證明或者直觀(guān)地感覺(jué)問(wèn)題與子問(wèn)題之間是否存在最優(yōu)子結(jié)構(gòu)性質(zhì)。從前往后分析。從序列長(zhǎng)度為1開(kāi)始，逐步放大序列長(zhǎng)度，2，3，4……看看要求的結(jié)果的變化規(guī)律。我們可能會(huì)很直接地想到，把問(wèn)題定義成當(dāng)前最長(zhǎng)不下降序列。序列長(zhǎng)度 序列 當(dāng)前最長(zhǎng)不下降序列長(zhǎng)度 1 13 1 2 137 1 3 1379 2 4 137916 3 5 13791638 4 6 1379163824 4（24<38,長(zhǎng)度不增加） 7 137916382427 ?(憑什么計(jì)算出當(dāng)前值？) 由于當(dāng)前記錄的最長(zhǎng)不下降序列是791638，而實(shí)際上應(yīng)該有了更長(zhǎng)的子序列79162427。我們定義F(i)為原始序列長(zhǎng)度為i的最長(zhǎng)不下降序列，則F(i)只有一個(gè)子問(wèn)題F(i-1)，即原始序列長(zhǎng)度為i-1的最長(zhǎng)不下降序列。而且我們無(wú)法得出問(wèn)題與子問(wèn)題之間的“最優(yōu)子結(jié)構(gòu)”性質(zhì)。13791638242738444921526315最長(zhǎng)不下降序列-分析重新思考關(guān)于問(wèn)題的定義。我們定義問(wèn)題F(i)為以bi結(jié)束的最長(zhǎng)不下降序列。則得到如下的分析結(jié)果：下標(biāo)i 序列 F(i) 前趨結(jié)點(diǎn)下標(biāo)13 1 1137 1 21379 2 2137916 3 313791638 4 41379163824 4 4137916382427 5 613791638242738 6 7 13791638242738444921526315最長(zhǎng)不下降序列-分析當(dāng)我們定義問(wèn)題F(i)為以bi結(jié)束的最長(zhǎng)不下降序列時(shí)，則問(wèn)題F(i)有i-1個(gè)子問(wèn)題：F(1),F(2),…,F(i-1)。我們要使F(i)最大，則要找到一個(gè)F(i)最大的子問(wèn)題，且同時(shí)滿(mǎn)足Bj<=Bi(1<j<i)，這時(shí)F(i):=F(j)+1例如F(4)有3個(gè)子問(wèn)題，分別是F(1),F(2),F(3),它們都滿(mǎn)足bj<bi的條件，而最大的F(j)=2,因此F(4):=F(3)+1=3,而它的前趨結(jié)點(diǎn)下標(biāo)是j13791638242738444921526315下標(biāo)I 序列 F(i) 前趨結(jié)點(diǎn)下標(biāo)13 1 1137 1 21379 2 2137916 3 313791638 4 41379163824 4 4137916382427 5 613791638242738 6 7最長(zhǎng)不下降序列-分析這樣定義問(wèn)題，我們就看到了“最優(yōu)子結(jié)構(gòu)”性質(zhì)。因此可以應(yīng)用動(dòng)態(tài)規(guī)劃方法求解問(wèn)題。請(qǐng)你分析本問(wèn)題的重疊子問(wèn)題性質(zhì)。請(qǐng)你遞歸地定義問(wèn)題的解。 F(i)=Max{F(j)+1|j<I且bj<=bi}本遞歸式的邊界條件是什么？ F(1)=1請(qǐng)你思考本題要求的結(jié)果是F(n)嗎？如果不是，那么最后要求的結(jié)果怎樣利用用動(dòng)態(tài)規(guī)劃求得的問(wèn)題和子問(wèn)題的值得到？怎樣輸出顯示最長(zhǎng)不下降序列的各個(gè)結(jié)點(diǎn)？13791638242738444921526315最長(zhǎng)不下降序列-討論如果從后向前分析原始序列，會(huì)得到正確的結(jié)果嗎？又該怎樣定義問(wèn)題？寫(xiě)出從后向前求最長(zhǎng)不下降序列的程序。13791638242738444921526315programupdown;{從前往后推}

vars,c,a:array[1..1000]ofinteger;

b:array[1..1000,1..1000]ofboolean;

t,i,j,k,n:integer;

begin

readln(n);

fillchar(a,sizeof(a),0);

fillchar(s,sizeof(s),0);

fillchar(b,sizeof(b),false);

fori:=1tondoreadln(a[i]);

s[1]:=1;

fori:=2tondo

begin

s[i]:=1;k:=i;

forj:=1toi-1do

if(a[j]<=a[i])and(s[j]+1>s[i])thenbegin

s[i]:=s[j]+1;k:=j;

end;

b[i,k]:=true;

end;

k:=0;j:=0;

fori:=ndownto1do

ifs[i]>kthenbegink:=s[i];j:=i;end;

i:=j;

writeln(k);

while(i>=1)and(s[j]>0)do

begin

c[s[j]]:=a[i];dec(s[j]);

fort:=i-1downto1do

if(b[i,t]=true)and(s[t]=s[j])thenbegini:=t;break;end;;

end;

fori:=1tokdowrite('',c[i]);

gramlongestnondecorder;{從后往前推}

type

int=longint;

var

a,b,c:array[1..50]ofint;

m,n,i,j,p,q:int;

max:int;

begin

readln(n);

fori:=1tondoread(a[i]);

b[n]:=1;c[n]:=0;

fori:=n-1downto1do

begin

max:=0;p:=0;

forj:=i+1tondo

if(a[i]<=a[j])and(b[j]>max)then

begin

p:=j;

max:=b[j];

end;

ifp<>0then

begin

b[i]:=b[p]+1;

c[i]:=p;

end

elsebeginb[i]:=1;c[i]:=0;end

end;

max:=0;p:=0;

fori:=1tondo

ifb[i]>maxthen

begin

max:=b[i];

p:=i

end;

whilep<>0dobeginwrite(a[p],'');p:=c[p];end;writeln;

writeln('max','',max);

end.思考：攔截導(dǎo)彈(NOIP1999提高組)某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來(lái)襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。

輸入導(dǎo)彈依次飛來(lái)的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

樣例：INPUT38920715530029917015865OUTPUT6（最多能攔截的導(dǎo)彈數(shù)）2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）[問(wèn)題分析]

第一部分是要求輸入數(shù)據(jù)串中的一個(gè)最長(zhǎng)不上升序列的長(zhǎng)度，可使用遞推的方法，具體做法是從序列的第一個(gè)元素開(kāi)始，依次求出以第i個(gè)元素為最后一個(gè)元素時(shí)的最長(zhǎng)不上升序列的長(zhǎng)度len(i)，遞推公式為len(1)=1，len(i)=max(len(j)+1)，其中i>1，j=1,2,…i-1，且j同時(shí)要滿(mǎn)足條件：序列中第j個(gè)元素大于等于第i個(gè)元素。第二部分比較有意思。由于它緊接著第一問(wèn)，所以很容易受前面的影響，采取多次求最長(zhǎng)不上升序列的辦法，然后得出總次數(shù)，其實(shí)這是不對(duì)的。要舉反例并不難，比如長(zhǎng)為7的高度序列“7541632”，最長(zhǎng)不上升序列為“75432”，用多次求最長(zhǎng)不上升序列的結(jié)果為3套系統(tǒng)；但其實(shí)只要2套，分別擊落“7541”與“632”。那么，正確的做法又是什么呢？我們的目標(biāo)是用最少的系統(tǒng)擊落所有導(dǎo)彈，至于系統(tǒng)之間怎么分配導(dǎo)彈數(shù)目則無(wú)關(guān)緊要；上面錯(cuò)誤的想法正是承襲了“一套系統(tǒng)盡量多攔截導(dǎo)彈”的思維定勢(shì)，忽視了最優(yōu)解中各個(gè)系統(tǒng)攔截?cái)?shù)較為平均的情況，本質(zhì)上是一種貪心算法。如果從每套系統(tǒng)攔截的導(dǎo)彈方面來(lái)想行不通的話(huà)，我們就應(yīng)該換一個(gè)思路，從攔截某個(gè)導(dǎo)彈所選的系統(tǒng)入手。題目告訴我們，已有系統(tǒng)目前的瞄準(zhǔn)高度必須不低于來(lái)犯導(dǎo)彈高度，所以，當(dāng)已有的系統(tǒng)均無(wú)法攔截該導(dǎo)彈時(shí)，就不得不啟用新系統(tǒng)。如果已有系統(tǒng)中有一個(gè)能攔截該導(dǎo)彈，我們是應(yīng)該繼續(xù)使用它，還是另起爐灶呢？事實(shí)是：無(wú)論用哪套系統(tǒng)，只要攔截了這枚導(dǎo)彈，那么系統(tǒng)的瞄準(zhǔn)高度就等于導(dǎo)彈高度，這一點(diǎn)對(duì)舊的或新的系統(tǒng)都適用。而新系統(tǒng)能攔截的導(dǎo)彈高度最高，即新系統(tǒng)的性能優(yōu)于任意一套已使用的系統(tǒng)。既然如此，我們當(dāng)然應(yīng)該選擇已有的系統(tǒng)。如果已有系統(tǒng)中有多個(gè)可以攔截該導(dǎo)彈，究竟選哪一個(gè)呢？當(dāng)前瞄準(zhǔn)高度較高的系統(tǒng)的“潛力”較大，而瞄準(zhǔn)高度較低的系統(tǒng)則不同，它能打下的導(dǎo)彈別的系統(tǒng)也能打下，它夠不到的導(dǎo)彈卻未必是別的系統(tǒng)所夠不到的。所以，當(dāng)有多個(gè)系統(tǒng)供選擇時(shí)，要選瞄準(zhǔn)高度最低的使用，當(dāng)然瞄準(zhǔn)高度同時(shí)也要大于等于來(lái)犯導(dǎo)彈高度。解題時(shí)，用一個(gè)數(shù)組記下已有系統(tǒng)的當(dāng)前瞄準(zhǔn)高度，數(shù)據(jù)個(gè)數(shù)就是系統(tǒng)數(shù)目。constmax=1000;vari,j,current,maxlong,minheight,select,tail,total:longint;height,longest,sys:array[1..max]oflongint;line:string;beginwrite('Inputtestdata:');readln(line);i:=1;whilei<=length(line)dobeginwhile(i<=length(line))and(line[i]='')doi:=i+1;current:=0;while(i<=length(line))and(line[i]<>'')dobegincurrent:=current*10+ord(line[i])-ord('0');i:=i+1end;total:=total+1;height[total]:=currentend;longest[1]:=1;fori:=2tototaldobeginmaxlong:=1;forj:=1toi-1dobeginifheight[i]<=height[j]theniflongest[j]+1>maxlongthenmaxlong:=longest[j]+1;

longest[i]:=maxlongend;end;maxlong:=longest[1];fori:=2tototaldoiflongest[i]>maxlongthenmaxlong:=longest[i];writeln(maxlong);sys[1]:=height[1];tail:=1;fori:=2tototaldobeginminheight:=maxint;forj:=1totaildoifsys[j]>height[i]thenifsys[j]<minheightthenbeginminheight:=sys[j];select:=jend;ifminheight=maxintthenbegintail:=tail+1;sys[tail]:=height[i]endelsesys[select]:=height[i]end;writeln(tail)end.例5：過(guò)河(NOIP2005)

在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長(zhǎng)度和青蛙一次跳過(guò)的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：0，1，……，L（其中L是橋的長(zhǎng)度）。坐標(biāo)為0的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為L(zhǎng)的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開(kāi)始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到T之間的任意正整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過(guò)坐標(biāo)為L(zhǎng)的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。題目給出獨(dú)木橋的長(zhǎng)度L，青蛙跳躍的距離范圍S,T，橋上石子的位置。你的任務(wù)是確定青蛙要想過(guò)河，最少需要踩到的石子數(shù)?！据斎胛募枯斎胛募iver.in的第一行有一個(gè)正整數(shù)L（1<=L<=109），表示獨(dú)木橋的長(zhǎng)度。第二行有三個(gè)正整數(shù)S，T，M，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中1<=S<=T<=10，1<=M<=100。第三行有M個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開(kāi)。【輸出文件】輸出文件river.out只包括一個(gè)整數(shù)，表示青蛙過(guò)河最少需要踩到的石子數(shù)?！緲永斎搿?023523567【樣例輸出】2【數(shù)據(jù)規(guī)模】對(duì)于30%的數(shù)據(jù)，L<=10000；對(duì)于全部的數(shù)據(jù)，L<=109。分析由于不能往回跳，很容易想到用動(dòng)態(tài)規(guī)劃解決這個(gè)題目。設(shè)f(i)表示跳到第i個(gè)點(diǎn)需要踩到的最少石子數(shù)，則很容易寫(xiě)出動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程:時(shí)間復(fù)雜度是O(L*(T-S))，但本題的L高達(dá)109，根本無(wú)法承受!

進(jìn)一步分析我們先來(lái)考慮這樣一個(gè)問(wèn)題：長(zhǎng)度為k的一段沒(méi)有石子的獨(dú)木橋，判斷是否存在一種跳法從一端正好跳到另一端。若S<T，事實(shí)上對(duì)于某個(gè)可跳步長(zhǎng)區(qū)間[S,T]，必然存在一個(gè)MaxK使得任何k>=MaxK，都可以從一端正好跳到另一端。題設(shè)中1<=S<=T<=10，經(jīng)過(guò)簡(jiǎn)單推導(dǎo)或者程序驗(yàn)證就可以發(fā)現(xiàn)，取MaxK=100就能滿(mǎn)足所有區(qū)間。于是我們可以分兩種情況討論：1.S=T時(shí)： 這時(shí)候由于每一步只能按固定步長(zhǎng)跳，所以若第i個(gè)位置上有石子并且imodS=0那么這個(gè)石子就一定要被踩到。這是我們只需要統(tǒng)計(jì)石子的位置中哪些是S的倍數(shù)即可。復(fù)雜度O(M)2.S<T時(shí)： 首先我們作如下處理：若存在某兩個(gè)相鄰石子之間的空白區(qū)域長(zhǎng)度>MaxK+2*T，我們就將這段區(qū)域縮短成長(zhǎng)度為MaxK+2*T。可以證明處理之后的最優(yōu)值和原先的最優(yōu)值相同。 ab如上圖所示，白色點(diǎn)表示連續(xù)的一長(zhǎng)段長(zhǎng)度大于MaxK+2*T的空地，黑色點(diǎn)表示石子。設(shè)原先的最優(yōu)解中，白色段的第一個(gè)被跳到的位置a，最后一個(gè)被跳到的位置是b，則在做壓縮處理之后，a和b的距離仍然大于MaxK，由上面的結(jié)論可知，必存在一種跳法從a正好跳到b，而且不經(jīng)過(guò)任何石子。所以原來(lái)的最優(yōu)解必然在處理之后的最優(yōu)解解集中。經(jīng)過(guò)這樣的壓縮處理，獨(dú)木橋的長(zhǎng)度L’最多為(M+1)*(MaxK+2*T)+M，大約12000左右。壓縮之后再用先前的動(dòng)態(tài)規(guī)劃求解，復(fù)雜度就簡(jiǎn)化成了O(L’*(T-S))，已經(jīng)可以在時(shí)限內(nèi)出解了。這樣本題就得到了解決。例6：花店櫥窗布置問(wèn)題(FLOWER)問(wèn)題描述

假設(shè)你想以最美觀(guān)的方式布置花店的櫥窗?，F(xiàn)在你有F束不同品種的花束，同時(shí)你也有至少同樣數(shù)量的花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從1至V順序編號(hào)，V是花瓶的數(shù)目，從左至右排列，則最左邊的是花瓶1，最右邊的是花瓶V?；ㄊ梢砸苿?dòng)，并且每束花用1至F間的整數(shù)唯一標(biāo)識(shí)。標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中的順序，如果I＜J，則令花束I必須放在花束J左邊的花瓶中。

例如，假設(shè)一束杜鵑花的標(biāo)識(shí)數(shù)為1，一束秋海棠的標(biāo)識(shí)數(shù)為2，一束康乃馨的標(biāo)識(shí)數(shù)為3，所有的花束在放入花瓶時(shí)必須保持其標(biāo)識(shí)數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個(gè)花瓶中只能放一束花。

每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個(gè)整數(shù)）來(lái)表示，空置花瓶的美學(xué)值為零。

在上述例子中，花瓶與花束的不同搭配所具有的美學(xué)值，如下表所示。

花

瓶12345花束1(杜鵑花)

723-5-24162(秋海棠)

521-4

10233(康乃馨)-21

5-4-2020例如，根據(jù)上表，杜鵑花放在花瓶2中，會(huì)顯得非常好看；但若放在花瓶4中則顯得十分難看。

為取得最佳美學(xué)效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。（2）假設(shè)條件

1≤F≤100，其中F為花束的數(shù)量，花束編號(hào)從1至F。

F≤V≤100，其中V是花瓶的數(shù)量。

-50≤Aij≤50，其中Aij是花束i在花瓶j中的美學(xué)值。

（3）輸入

輸入文件是正文文件（textfile），文件名是flower.inp。

第一行包含兩個(gè)數(shù)：F，V。

隨后的F行中，每行包含V個(gè)整數(shù)，Aij即為輸入文件中第（i+1）行中的第j個(gè)數(shù)。

（4）輸出

輸出文件必須是名為flower.out的正文文件，文件應(yīng)包含兩行：

第一行是程序所產(chǎn)生擺放方式的美學(xué)值。

第二行必須用F個(gè)數(shù)表示擺放方式，即該行的第K個(gè)數(shù)表示花束K所在的花瓶的編號(hào)。（5）例子

flower.in：

35

723–5–2416

521-41023

-215-4-2020

flower.out：

53

245

（6）評(píng)分

程序必須在2秒中內(nèi)運(yùn)行完畢。

在每個(gè)測(cè)試點(diǎn)中，完全正確者才能得分。

花店櫥窗布置（IOI’99）花瓶12345花束1、杜鵑花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020花瓶12345花束1、杜鵑花72323-∞-∞2、秋海棠-∞282833-∞3、康乃馨-∞-∞242453F[i，j]=前i束花放入前j個(gè)花瓶?jī)?nèi)的最大美學(xué)價(jià)值（花i不一定必須插在瓶j內(nèi)）。目標(biāo):f[n,m]花瓶12345花束1、杜鵑花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020a[I,j]f[I,j]分析：方法一A[i,j]=花i放入j瓶的美學(xué)價(jià)值。F[i，j]=前i束花放入前j個(gè)花瓶?jī)?nèi)的最大美學(xué)價(jià)值（花i不一定必須插在瓶j內(nèi)）。計(jì)算F[I,j]有兩種情況：1):花i放入第j個(gè)花瓶中：F[i，j]=f[i-1,j-1]+a[i,j]2):花i不放入第j個(gè)花瓶中,只能放在前j-1個(gè)花瓶?jī)?nèi)：F[i，j]=f[i,j-1]動(dòng)態(tài)轉(zhuǎn)移方程：F[i，j]＝max｛f[i-1,j-1]+a[i,j]，f[i,j-1]｝初始化：f[i,i]=a[1,1]+a[2,2]+…+a[i,i];目標(biāo)：f[n,m]容易理解的方法：fillchar(f,sizeof(f),0);f[1,1]:=a[1,1];fori:=2tondof[i,i]:=f[i-1,i-1]+a[i,i];fori:=1tondoforj:=i+1tom-(n-i)dof[i,j]:=max(f[i,j-1],f[i-1,j-1]+a[i,j]);分析：方法二：a,f:array[0..maxn,0..maxm]ofinteger;a[i,j]表示第i束花插到第j個(gè)花瓶中的價(jià)值；f[i,j]表示第i束花插到第j個(gè)花瓶后，也就是說(shuō)：第i束花插在第ｊ個(gè)花瓶，前i-1束花插在前ｊ-１個(gè)花瓶?jī)?nèi)所獲得的價(jià)值和的最大值。動(dòng)態(tài)轉(zhuǎn)移方程：

f[i,j]＝max{f[i-1,k]}+a[i,j](i-1<=k<=j-1)枚舉第i-1束花所在的花瓶k初始化：f[0,0]=0;f[i,0]=-∞(1<=i<=n)目標(biāo)：max{f[n,i]}(1<=i<=m)算法設(shè)計(jì)flower一題是IOI99第一天第一題，該題如用組合的方法處理，將會(huì)造成超時(shí)。正確的方法是用動(dòng)態(tài)規(guī)劃，考慮角度為一束一束地增加花束，假設(shè)用b(i,j)表示1～i束花放在1到j(luò)之間的花瓶中的最大美學(xué)值，其中i<=j，則b(i,j)=max(b[i-1,k-1]+A[i,k])，其中i<=k<=j，A(i,k)的含義參見(jiàn)題目。輸出結(jié)果時(shí)，顯然使得b[F,k]取得總的最大美觀(guān)值的第一個(gè)k值就是第F束花應(yīng)該擺放的花瓶位置，將總的最大美觀(guān)值減去A[i,k]的值即得到前k-1束花放在前k-1個(gè)瓶中的最大美觀(guān)值，依次使用同樣的方法就可求出每一束花應(yīng)該擺放的花瓶號(hào)。由于這一過(guò)程是倒推出來(lái)的，所以程序中用遞歸程序來(lái)實(shí)現(xiàn)。programex8_4(input,output);

constmax=100;

var

f,v,i,j,k,cmax,current,max_val:integer;

table,val:array[1..max,1..max]ofinteger;

fname:string;

fin:text;

procedureprint(current,max_val:integer);

vari:integer;

begin

ifcurrent>0then

begin

i:=current;

whileval[current,i]<>max_valdoi:=i+1;

print(current-1,max_val-table[current,i]);

write(i,'')

end

end;begin

write('Inputthefilenameoftestdata:');

readln(fname);

assign(fin,fname);

reset(fin);

readln(fin,f,v);

fori:=1tofdo

begin

forj:=1tovdoread(fin,table[i,j]);

readln(fin);

end;

close(fin);

max_val:=-maxint;

fori:=1tovdo

ifmax_val<table[1,i]

thenbeginval[1,i]:=table[1,i];max_val:=table[1,i]end

elseval[1,i]:=table[1,i];fori:=2tofdo

forj:=itov-f+ido

begin

max_val:=-maxint;

fork:=i-1toj-1do

begin

cmax:=-maxint;

forcurrent:=k+1tojdo

iftable[i,current]>cmaxthencmax:=table[i,current];

ifcmax+val[i-1,k]>max_valthenmax_val:=cmax+val[i-1,k]

end;

val[i,j]:=max_val

end;

max_val:=-maxint;

fori:=ftovdo

ifval[f,i]>max_valthenmax_val:=val[f,i];

writeln(max_val);

print(f,max_val);

writeln

end.

思考：機(jī)器分配（HNOI’95）問(wèn)題描述總公司擁有高效生產(chǎn)設(shè)備M臺(tái)，準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備，可以為國(guó)家提供一定的盈利。問(wèn)：如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大？求出最大盈利值。其中M《=15，N〈=10。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過(guò)總設(shè)備數(shù)M。保存數(shù)據(jù)的文件名從鍵盤(pán)輸入。數(shù)據(jù)文件格式為：第一行保存兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二個(gè)數(shù)是分公司數(shù)N。接下來(lái)是一個(gè)M*N的矩陣，表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。樣例輸入：34101526302032384312202735樣例輸出：54分析：F[i,j]:前i個(gè)公司分配j臺(tái)機(jī)器獲得的最大盈利。試試看：F[1,1],f[1,2]……f[1,m].F[2,1],f[2,2]……f[2,m].。。。動(dòng)態(tài)轉(zhuǎn)移方程：f[i,j]=max{f[i-1,j-k]+a[i,k]}(1<=i<=n,1<=j<=m,0<=k<=j)初始：f[1,i]:=a[1,i]i:1……m目標(biāo)：f[n,m]fori:=1tomdof[1,i]:=a[1,i];fori:=2tondoforj:=1tomdofork:=0tojdof[i,j]:=max(f[i,j],f[i-1,j-k]+a[i,k]);格式一：fori:=1tondoforj:=1tomdofork:=0tojdof[i,j]:=max(f[i,j],f[i-1,j-k]+a[i,k]);格式二：動(dòng)態(tài)歸劃與一般遞推的異同動(dòng)態(tài)規(guī)劃和一般遞推相同點(diǎn)在于:

1、無(wú)后效性

2、有邊界條件不同點(diǎn)在于:

1、一般遞推邊界條件很明顯,動(dòng)態(tài)規(guī)劃邊界條件比較隱蔽,容易被忽視

2、一般遞推數(shù)學(xué)性較強(qiáng),動(dòng)態(tài)規(guī)劃數(shù)學(xué)性相對(duì)較弱

3、一般遞推一般不劃分階段,動(dòng)態(tài)規(guī)劃一般有較為明顯的階段動(dòng)態(tài)規(guī)劃一般遞推關(guān)系遞推關(guān)系在實(shí)際應(yīng)用中，許多問(wèn)題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來(lái)說(shuō)，只要該問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解（即滿(mǎn)足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃將原來(lái)具有指數(shù)級(jí)復(fù)雜度的搜索算法改進(jìn)成了具有多項(xiàng)式時(shí)間的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過(guò)程中，不得不存儲(chǔ)產(chǎn)生過(guò)程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。DP與其它算法的同異動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類(lèi)似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。其中貪心法的當(dāng)前選擇可能要依賴(lài)已經(jīng)作出的所有選擇，但不依賴(lài)于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問(wèn)題是獨(dú)立的(即不包含公共的子問(wèn)題)，因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。但不足的是，如果當(dāng)前選擇可能要依賴(lài)子問(wèn)題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。動(dòng)態(tài)規(guī)劃法所針對(duì)的問(wèn)題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把答案保存起來(lái)，讓以后再遇到時(shí)直接引用，不必重新求解。

例7：最長(zhǎng)公共子序列LCS一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說(shuō)，若給定序列X=<x1,x2,…,xm>，則另一序列Z=<z1,z2,…,zk>是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列<i1,i2,…,ik>，使得對(duì)于所有j=1,2,…,k有例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相應(yīng)的遞增下標(biāo)序列為<2,3,5,7>。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，則序列<B,C,A>是X和Y的一個(gè)公共子序列，序列<B,C,B,A>也是X和Y的一個(gè)公共子序列。而且，后者是X和Y的一個(gè)最長(zhǎng)公共子序列，因?yàn)閄和Y沒(méi)有長(zhǎng)度大于4的公共子序列。給定兩個(gè)序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一個(gè)最長(zhǎng)公共子序列。輸入輸入文件共有兩行，每行為一個(gè)由大寫(xiě)字母構(gòu)成的長(zhǎng)度不超過(guò)200的字符串，表示序列X和Y。輸出輸出文件第一行為一個(gè)非負(fù)整數(shù)，表示所求得的最長(zhǎng)公共子序列的長(zhǎng)度，若不存在公共子序列，則輸出文件僅有一行輸出一個(gè)整數(shù)0，否則在輸出文件的第二行輸出所求得的最長(zhǎng)公共子序列(也用一個(gè)大寫(xiě)字母組成的字符串表示)，若符合條件的最長(zhǎng)公共子序列不止一個(gè)，只需輸出其中任意的一個(gè)。樣例lcs.inABCBDABBDCABAlcs.out4BCBA評(píng)分標(biāo)準(zhǔn)若輸出的最長(zhǎng)公共子序列的長(zhǎng)度正確，則得5分；若輸出的最長(zhǎng)公共子序列也正確，則再得5分。窮舉解最長(zhǎng)公共子序列問(wèn)題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X的每一個(gè)子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列。X的所有子序列都檢查過(guò)后即可求出X和Y的最長(zhǎng)公共子序列。X的一個(gè)子序列相應(yīng)于下標(biāo)序列{1,2,…,m}的一個(gè)子序列，因此，X共有2m個(gè)不同子序列，從而窮舉搜索法需要指數(shù)時(shí)間。定理:LCS的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一個(gè)最長(zhǎng)公共子序列Z=<z1,z2,…,zk>，則：若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列；若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長(zhǎng)公共子序列；若xm≠yn且zk≠yn，則Z是X和Yn-1的最長(zhǎng)公共子序列。其中Xm-1=<x1,x2,…,xm-1>，Yn-1=<y1,y2,…,yn-1>，

Zk-1=<z1,z2,…,zk-1>。分析描述LCS問(wèn)題最優(yōu)解的結(jié)構(gòu)首先．我們給出一個(gè)字符串“前綴”的概念：給定一個(gè)字符串X=<X1,X2,…,Xm>，對(duì)I=0,1,…,m，定義X的第i個(gè)前綴為例如，如果X＝＜A，B，C，B，D，A，B＞，則而則為空串。兩個(gè)輸入字符串X和Y的所有前綴組成了LCS問(wèn)題的子問(wèn)題空間。由此我們發(fā)現(xiàn)LCS問(wèn)題的最優(yōu)子結(jié)構(gòu)的三個(gè)性質(zhì)：設(shè)X＝<X1,X2,…,Xm>和Y＝<Y1,Y2,…,Yn>為兩個(gè)輸入字符串，并設(shè)X和Y的最長(zhǎng)公共子串為Z=<Z1,Z2,…,Zk>性質(zhì)1：如果Xm=Yn，則Zk=Xm=Yn，且也就是說(shuō)，如果兩個(gè)字符串最后一位字符相等，則它們的最長(zhǎng)公共子串的最后一位就是這個(gè)字符，并且公共子串的第k-1個(gè)前綴是兩個(gè)字符串前綴的最長(zhǎng)公共子串分析舉例說(shuō)明： X=<A,B,E,…,G,F> Y=<C,D,H,…,K,F>因X和Y的最后一位相等，則它們的最長(zhǎng)公共子串Z的最后一位必為F，即有Z=<……,F>的樣式。并且Z’=<……>是X’=<A,B,E,…,G>和Y’=<C,D,H,…,K>的最長(zhǎng)公共子串。性質(zhì)2：也就是說(shuō)，如果兩個(gè)字符串最后一位不等，則它們的最長(zhǎng)公共子串Z的最后一位不等于X的最后一位，就意味著Z是X的前綴與Y的最長(zhǎng)公共子串。舉例說(shuō)明：X=<A,B,E,…,G,M>Y=<C,D,H,…,K,S>Z=<……,F>因X和Y最后一位不等，X和它的子串的最后一位也不等，則Z是X’=<A,B,E…,G>和Y的最長(zhǎng)公共子串分析-最優(yōu)子結(jié)構(gòu)性質(zhì)3：也就是說(shuō)，如果兩個(gè)字符串最后一位不等，則它們的最長(zhǎng)公共子串Z的最后一位不等于Y的最后一位，就意味著Z是X與Y的前綴的最長(zhǎng)公共子串。舉例說(shuō)明：X=<A,B,E,…,G,W>Y=<C,D,H,…,K,I>Z=<……,F>因X和Y最后一位不等，Y和它的子串的最后一位也不等，則Z是X和Y’=<C,D,H,…K>的最長(zhǎng)公共子串由此可見(jiàn)，字符串X和Y的一個(gè)最長(zhǎng)公共子串也是包含了兩個(gè)字符串的前綴的一個(gè)最長(zhǎng)公共子串，這就說(shuō)明了LCS問(wèn)題具備最優(yōu)子結(jié)構(gòu)性質(zhì)。證明1.用反證法。若zk≠xm，則<z1,z2,…,zk,xm>是X和Y的長(zhǎng)度為k十1的公共子序列。這與Z是X和Y的一個(gè)最長(zhǎng)公共子序列矛盾。因此，必有zk=xm=yn。由此可知Zk-1是Xm-1和Yn-1的一個(gè)長(zhǎng)度為k-1的公共子序列。若Xm-1和Yn-1有一個(gè)長(zhǎng)度大于k-1的公共子序