動(dòng)態(tài)規(guī)劃步驟

動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。

根據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算，實(shí)現(xiàn)的大體上的框架如下：

1標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框架

1.對(duì)fn+1(xn+1)初始化;{邊界條件}

2.fork:=ndownto1do

3.for每一個(gè)xk∈Xkdo

4.for每一個(gè)uk∈Uk(xk)do

begin

5.fk(xk):=一個(gè)極值;{∞或－∞}

6.xk+1:=Tk(xk,uk);{狀態(tài)轉(zhuǎn)移方程}

7.t:=φ(fk+1(xk+1),vk(xk,uk));{基本方程(9)式}

8.ift比f(wàn)k(xk)更優(yōu)thenfk(xk):=t;{計(jì)算fk(xk)的最優(yōu)值}

end;

9.t:=一個(gè)極值;{∞或－∞}

10.for每一個(gè)x1∈X1do

11.iff1(x1)比t更優(yōu)thent:=f1(x1);{按照10式求出最優(yōu)指標(biāo)}

12.輸出t;2但是，實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)

步驟進(jìn)行：

1.分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。

2.遞歸地定義最優(yōu)值。

3.以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。

4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。

步驟(1)--(3)是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟(4)

可以省略，若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟(4)。此時(shí)，在步驟

(3)中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的

信息，快速地構(gòu)造出一個(gè)最優(yōu)解。3城市街道問(wèn)題：456【例題4】合唱隊(duì)形【問(wèn)題描述】N位同學(xué)站成一排，音樂老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1,2,…,K，他們的身高分別為T1,T2,…,TK，則他們的身高滿足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in的第一行是一個(gè)整數(shù)N（2≤N≤100），表示同學(xué)的總數(shù)。第二行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti（130≤Ti≤230）是第i位同學(xué)的身高（厘米）?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186186150200160130197220【樣例輸出】4【數(shù)據(jù)規(guī)模】對(duì)于50%的數(shù)據(jù)，保證有n≤20；對(duì)于全部的數(shù)據(jù)，保證有n≤100。7【算法分析】我們按照由左而右和由右而左的順序，將n個(gè)同學(xué)的身高排成數(shù)列。如何分別在這兩個(gè)數(shù)列中尋求遞增的、未必連續(xù)的最長(zhǎng)子序列，就成為問(wèn)題的關(guān)鍵。設(shè)a為身高序列，其中a[i]為同學(xué)i的身高；b為由左而右身高遞增的人數(shù)序列，其中b[i]為同學(xué)1‥同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然b[i]={b[j]|同學(xué)j的身高<同學(xué)i的身高}+1；c為由右而左身高遞增的人數(shù)序列，其中c[i]為同學(xué)n‥同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然c[i]={c[j]|同學(xué)j的身高<同學(xué)i的身高}+1；由上述狀態(tài)轉(zhuǎn)移方程可知，計(jì)算合唱隊(duì)形的問(wèn)題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使b[i]和c[i]最大，子問(wèn)題的解b[j]和c[k]必須最大(1≤j≤i-1，i+1≤k≤n))和重迭子問(wèn)題的性質(zhì)(為求得b[i]和c[i]，必須一一查閱子問(wèn)題的解b[1]‥b[i-1]和c[i+1]‥c[n])，因此可采用動(dòng)態(tài)程序設(shè)計(jì)的方法求解。顯然，合唱隊(duì)的人數(shù)為(公式中同學(xué)i被重復(fù)計(jì)算，因此減1)，n減去合唱隊(duì)人數(shù)即為解。8出列人數(shù)最少，也就是說(shuō)留的人最多，也就是序列最長(zhǎng)。這樣分析就是典型的最長(zhǎng)下降子序列問(wèn)題。只要枚舉每一個(gè)人站中間時(shí)可以的到的最優(yōu)解。顯然它就等于，包括他在內(nèi)向左求最長(zhǎng)上升子序列，向右求最長(zhǎng)下降子序列。我們看一下復(fù)雜度：計(jì)算最長(zhǎng)下降子序列的復(fù)雜度是O（N2），一共求N次，總復(fù)雜度是O（N3）。這樣的復(fù)雜度對(duì)于這個(gè)題的數(shù)據(jù)范圍來(lái)說(shuō)是可以AC的。但有沒有更好的方法呢？其實(shí)最長(zhǎng)子序列只要一次就可以了。因?yàn)樽铋L(zhǎng)下降（上升）子序列不受中間人的影響。只要用OPT1求一次最長(zhǎng)上升子序列，OPT2求一次最長(zhǎng)下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).復(fù)雜度由O（N3）降到了O（N2）?！舅惴ǚ治觥?【問(wèn)題描述】PALMIA國(guó)家被一條河流分成南北兩岸，南北兩岸上各有N個(gè)村莊。北岸的每一個(gè)村莊有一個(gè)唯一的朋友在南岸，且他們的朋友村莊彼此不同。每一對(duì)朋友村莊想要一條船來(lái)連接他們，他們向政府提出申請(qǐng)以獲得批準(zhǔn)。由于河面上常常有霧，政府決定禁止船只航線相交（如果相交，則很可能導(dǎo)致碰船）。你的任務(wù)是編寫一個(gè)程序，幫助政府官員決定批準(zhǔn)哪些船只航線，使得不相交的航線數(shù)目最大。船

10【輸入文件】ships.in輸入文件由幾組數(shù)據(jù)組成。每組數(shù)據(jù)的第一行有2個(gè)整數(shù)X，Y，中間有一個(gè)空格隔開，X代表PALMIA河的長(zhǎng)度（10<=X<=6000），Y代表河的寬度（10<=Y<=100）。第二行包含整數(shù)N，表示分別坐落在南北兩岸上的村莊的數(shù)目（1<=N<=5000）。在接下來(lái)的N行中，每一行有兩個(gè)非負(fù)整數(shù)C，D，由一個(gè)空格隔開，分別表示這一對(duì)朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最后一組數(shù)據(jù)的下面僅有一行，是兩個(gè)0，也被一空格隔開。【輸出文件】ships.out對(duì)輸入文件的每一組數(shù)據(jù)，輸出文件應(yīng)在連續(xù)的行中表示出最大可能滿足上述條件的航線的數(shù)目?！据斎霕永?0472242610315129817174200【輸出樣例】411【問(wèn)題分析】這道題目相對(duì)來(lái)說(shuō)思考難度較高，從字面意義上看不出問(wèn)題的本質(zhì)來(lái)，有點(diǎn)無(wú)法下手的感覺。尋找規(guī)律自然要推幾組數(shù)據(jù)，首先當(dāng)然有從樣例入手；仔細(xì)觀察上圖：紅色航線是合法的，那么他們滿足什么規(guī)律呢？C1

C2

C3

C4北岸紅線的端點(diǎn)：4

9

15

17南岸紅線的端點(diǎn)：2

8

12

17D1

D2

D3

D4不難看出無(wú)論線的斜率如何，都有這樣的規(guī)律：C1<C2<C3<C4且

D1<D2<D3<D412如果我們把輸入數(shù)據(jù)排升序，問(wèn)題變抽象為：在一個(gè)序列（D）里找到最長(zhǎng)的序列滿足DI<DJ<Dk……且i<j<k這樣的話便是典型的最長(zhǎng)非降子序列問(wèn)題了。。。。法二：邊界條件法邊界法其實(shí)就是把數(shù)據(jù)往小了縮，顯然N=1是答案是1。N=2時(shí)呢？考慮這樣一組數(shù)據(jù)：N=2C1

D1C2

D2當(dāng)C1<C2時(shí)，如果D1>D2那么一定會(huì)相交，反之則不會(huì)相交。當(dāng)C1

>C2時(shí)，如果D1<D2那么一定會(huì)相交，反之則不會(huì)相交。N=3C1

D1C2

D2C3

D3……其實(shí)不用在推導(dǎo)N=3了，有興趣的可以推導(dǎo)去?？碞=2時(shí)就能得出：對(duì)于任意兩條航線如果滿足Ci<Cj且Di<Dj則兩條航線不相交。這樣的話要想在一個(gè)序列里讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans且D1<D2<D3…<Dans，也就是將C排序后求出最長(zhǎng)的滿足這個(gè)條件的序列的長(zhǎng)度就是解。這樣分析后顯然是一個(gè)最長(zhǎng)非降子序列問(wèn)題。復(fù)雜度：排序可以用O（nlogn）的算法，求最長(zhǎng)非降子序列時(shí)間復(fù)雜度是O(n2).總復(fù)雜度為O（n2）.13背包問(wèn)題0/1背包【問(wèn)題描述】一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價(jià)值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價(jià)值?！据斎敫袷健康谝恍校簝蓚€(gè)整數(shù)，M(背包容量，M<=200)和N(物品數(shù)量，N<=30)；第2..N+1行：每行二個(gè)整數(shù)Wi,Ci，表示每個(gè)物品的重量和價(jià)值?！据敵龈袷健?jī)H一行，一個(gè)數(shù)，表示最大總價(jià)值?！緲永斎搿縫ackage.in10421334579【樣例輸出】package.out1214【解法一】【算法分析】設(shè)f(i，x)表示前i件物品，總重量不超過(guò)x的最優(yōu)價(jià)值，則f(i，x)=max(f(i-1，x-w[i])+c[i],f(i-1，x）)；f（n，m）即為最優(yōu)解。下面例出F[I，X]的值，I表示前I件物品，X表示重量【參考程序】(順推法)programpackage;constmaxm=200;maxn=30;varm,n,x,i:integer;c,w:array[1..maxn]ofinteger;f:array[0..maxn,0..maxm]ofinteger;functionmax(x,y:integer):integer;//求x和y最大值beginifx>ythenmax:=xelsemax:=y;end;15BEGINassign(input,'package.in');assign(output,'package.out');reset(input);rewrite(output);readln(m,n);//背包容量m和物品數(shù)量nfori:=1tondoreadln(w[i],c[i]);//每個(gè)物品的重量和價(jià)值fori:=1tondoforx:=1tomdobegin//f(i，x)表示前i件物品，總重量不超過(guò)x的最優(yōu)價(jià)值ifx>=w[i]thenf[i,x]:=max(f[i-1,x-w[i]]+c[i],f[i-1,x])elsef[i,x]:=f[i-1,x];end;writeln(f[n,m]);//f(n，m)為最優(yōu)解close(input);close(output);END.使用二維數(shù)組存儲(chǔ)各子問(wèn)題時(shí)方便，但當(dāng)maxm較大時(shí)如maxn=2000時(shí)不能定義二維數(shù)組f,怎么辦,其實(shí)可以用一維數(shù)組。16【解法二】【算法分析】本問(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。下面例出F[x]表示重量不超過(guò)x公斤的最大價(jià)值，x表示重量F[x]F[1]F[2]F[3]F[4]F[5]F[6]F[7]F[8]F[9]F[10]I=10111111111I=20133444444I=30135568899I=401355699101217【參考程序】programstar_package;Vari,x,k,n,m:longint;f:array[0..100000]oflongint;w,c:array[0..2000]oflongint;beginassign(input,'package.in');assign(output,'package.out');reset(input);rewrite(output);fillchar(f,sizeof(f),0);readln(m,n);//背包容量m和物品數(shù)量nfori:=1tondoreadln(w[i],c