高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 動(dòng)態(tài)規(guī)劃實(shí)例分析及程序?qū)崿F(xiàn)

1、全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽動(dòng)態(tài)規(guī)劃實(shí)例分析及程序?qū)崿F(xiàn)一、數(shù)字三角形（圖.）示出了一個(gè)數(shù)字三角形。 請(qǐng)編一個(gè)程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。每一步可沿左斜線向下或右斜線向下走；1三角形行數(shù)100；三角形中的數(shù)字為整數(shù)0，1，99；輸入數(shù)據(jù)：由INPUT.TXT文件中首先讀到的是三角形的行數(shù)。在例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5輸出數(shù)據(jù)：把最大總和（整數(shù)）寫入OUTPUT.TXT文件。上例為：30（圖.） 二、算法分析只要對(duì)該題稍加分析，就可以得出一個(gè)結(jié)論：如果得到一條由頂至底的某處的一條最佳路徑，那么對(duì)于該路

2、徑上的每一個(gè)中間點(diǎn)來說，由頂至該中間點(diǎn)的路徑所經(jīng)過的數(shù)字和也為最大。因此該題是一個(gè)典型的多階段決策最優(yōu)化的問題。我們采用動(dòng)態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段。若行數(shù)為n, 則可把問題看作一個(gè)n-1個(gè)階段的決策問題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階段，第n-1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終點(diǎn)的最佳路徑。設(shè)：k（k）從第階段中的點(diǎn)k至三角形頂點(diǎn)有一條最佳路徑， 該路徑所經(jīng)過的數(shù)字的總和最大，k（k）表示為這個(gè)數(shù)字和；由于每一次決策有兩個(gè)選擇，或沿左斜線向下，或沿右斜線向下，因此設(shè)k1階段中某點(diǎn)k沿左斜線向下的點(diǎn)；k2階段中某點(diǎn)k沿右斜線向下的點(diǎn)；k（k1）階段中k1的

3、數(shù)字；k（k2）階段中k2的數(shù)字；因而可寫出順推關(guān)系式k（k）k-1（k）k（k1），k-1（k）k（k2）0（0）；，經(jīng)過一次順推，便可分別求出由頂至底個(gè)數(shù)的條路徑，在這條路徑所經(jīng)過的個(gè)數(shù)字和中，最大值即為正確答案。 三、程序分析根據(jù)上述順推關(guān)系，我們編寫程序如下：Program ID1P1;ConstMaxn = 100;TypeNode = RecordVal, Tot : Integer 當(dāng)前格數(shù)字; 從1,1到當(dāng)前格的路徑所經(jīng)過的數(shù)字和 End;VarList : Array 1.Maxn, 1.Maxn of Node; 計(jì)算表 N, Max, 行數(shù), 最大總和 I, J : In

4、teger; 輔助變量 Fi : Text; 文件變量 Procedure Init;BeginAssign(Fi, INPUT.TXT); 文件名和文件變量連接 Reset(Fi); 文件讀準(zhǔn)備 Readln(Fi, N); 讀三角形行數(shù) For i := 1 to N Do 讀入三角形各格的數(shù)字 For j := 1 to i Do Read(Fi, Listi, j.Val);Close(Fi)End;initProcedure Main;BeginList1, 1.Tot := List1, 1.Val; 從1,1位置開始往下順推 For i := 2 to N DoFor j :=

5、1 to i Do BeginListi, j.Tot := -1; 從1,1至i,j的數(shù)字和初始化 If (j 1) And(Listi - 1, j - 1.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j - 1.Tot + Listi, j.Val; 若從i-1,j-1選擇右斜線向下會(huì)使1,1至i,j的數(shù)字和最大,則決策該步 If (j i) And(Listi - 1, j.Tot + Listi, j.Val Listi, j.Tot) ThenListi, j.Tot := Listi - 1, j

6、.Tot + Listi, j.Val 若從i-1,j選擇左斜線向下會(huì)使1,1至i,j的數(shù)字和最大,則決策該步 End; forMax := 1; 1,1至底行各點(diǎn)的N條路徑所經(jīng)過的數(shù)字和中,選擇最大的一個(gè)輸出 For i := 2 to N Do If ListN, i.Tot ListN, Max.Tot ThenMax := i;Writeln(ListN, Max.Tot) 輸出最大總和 End; mainBeginInit; 讀入數(shù)字三角形 Main 求最大總和 End.main 二、Problem : 打鼴鼠Contents: 有個(gè)n*n個(gè)格子，在m個(gè)時(shí)間點(diǎn)上的不定格子里有數(shù)量不等

7、的鼴鼠出現(xiàn)，機(jī)器人每次只能向前后左右移動(dòng)一個(gè)格子，問最多機(jī)器人能打多少鼴鼠？ (n=1000, m=10000)Type: 動(dòng)態(tài)規(guī)劃 Difficulty: 2 Source: HNOI2004_day_*_*Solution : a) 記得學(xué)OI不到幾個(gè)月，高一剛上來就做的這道題.著實(shí)郁悶了半天,有一個(gè)思路是開1000*1000 的數(shù)組亂搞忘了可以過幾個(gè)來著.b) 又翻到這道題的時(shí)候是2月份了.發(fā)現(xiàn) fi表示：如果機(jī)器人最后打死的老鼠是第i只，這種情況下機(jī)器人最多可以打死多少老鼠。就可以了,然后我赫然發(fā)現(xiàn)108 div 2次的若干基本操作是要TLE的c) 鑒于這道題郁悶的理論時(shí)間復(fù)雜度無法優(yōu)

8、化，我請(qǐng)教了朱老師，原來動(dòng)態(tài)規(guī)劃枚舉順序也有其優(yōu)化技巧，由于思路不是自己的，僅作簡(jiǎn)要介紹：a) (1).將更快、更容易“短路”的判斷放在前面b) (2).將內(nèi)部循環(huán)（j的循環(huán)）倒序，逼近最優(yōu)解d) 我的計(jì)算機(jī)有點(diǎn)慢 總分 = 100.0第一題：mole 得分 = 100.0 用時(shí) = 7.16smole-0(mole1.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 0.01s 空間 = 0.71Mmole-1(mole2.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 0.01s 空間 = 0.71Mmole-2(mole3.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) =

9、0.02s 空間 = 0.71Mmole-3(mole4.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 0.98s 空間 = 0.71Mmole-4(mole5.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.02s 空間 = 0.71Mmole-5(mole6.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.00s 空間 = 0.71Mmole-6(mole7.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.05s 空間 = 0.71Mmole-7(mole8.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.02s 空間 = 0.71Mmole

10、-8(mole9.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.02s 空間 = 0.71Mmole-9(mole10.In) 結(jié)果 = 正確 得分 = 10.0 用時(shí) = 1.02s 空間 = 0.71M分析設(shè)第i只老鼠在第Ti個(gè)時(shí)刻出現(xiàn)在(xi, yi)，T1=T2=T3=Tm。假設(shè)機(jī)器人打死了L只老鼠，不妨設(shè)這些老鼠的編號(hào)是a1, a2, , aL。顯然對(duì)于任意的i(1=i=|xai+1-xai|+|yai+1-yai|。fi表示：如果機(jī)器人最后打死的老鼠是第i只，這種情況下機(jī)器人最多可以打死多少老鼠。可以列出方程：fi = maxfj+1, 11=j=|xi-xj|+|yi

11、-yj|最后求的答案就是maxfi(1=i=m) 此算法時(shí)間復(fù)雜度為O(m2)。考慮到m=10000，而時(shí)限只有1second，所以還必須進(jìn)行一些代碼優(yōu)化。 因?yàn)閖i，所以實(shí)際的循環(huán)次數(shù)只有m2/2次，也就是至多5000萬左右。 我們看看下面的代碼：for i := 1 to m do begin fi := 0; for j := 1 to i 1 do if (abs(xi-xj) + abs(yi-yj) fi) then fi := fj; fi:=fi+1;end; 它無疑是正確的。但是循環(huán)中的判斷語句大有文章可做：上面的代碼每次都鐵定至少要執(zhí)行3次減法、2次絕對(duì)值、1次比較運(yùn)算。這

12、無疑是極度昂貴的操作代價(jià)。所以我們可以將(fjfi)這個(gè)比較“便宜”的判斷條件提到前面，變成如下形式： if (fjfi) and (abs(xi-xj) + abs(yi-yj)=Ti-Tj) then這樣做的好處是一旦fj=fi就可以執(zhí)行“短路操作”（也就是說后面那一大截速度很慢的操作都可以避免。不過編譯的時(shí)候一定要記得設(shè)成$B+） 實(shí)踐證明速度是快了不少?？墒菍?duì)于1second的時(shí)限還是不能勝任。實(shí)戰(zhàn)游戲經(jīng)驗(yàn)告訴我們，機(jī)器人一般情況下不可能打完一只老鼠之后就跑到很遠(yuǎn)的地方去尋找新的獵物，肯定是一路上碰到一點(diǎn)老鼠就打一點(diǎn)。所以機(jī)器人相繼打的兩只老鼠的出現(xiàn)時(shí)間不可能相差太遠(yuǎn)。因此在方程fi

13、= maxfj+1, 11=j=|xi-xj|+|yi-yj|之中，使得i達(dá)到最優(yōu)的j肯定不會(huì)和i差得太遠(yuǎn)。同時(shí)在我們的判斷語句中：if (fjfi) and (abs(xi-xj) + abs(yi-yj)fi) and (abs(xi-xj) + abs(yi-yj)fi) and (abs(xi-xj)+abs(yi-yj)ans then ans:=fi; end; assign(output,mole.out); rewrite(output); writeln(ans); close(output);END. 三、最大連續(xù)子序列給出一個(gè)長(zhǎng)度為n 的整數(shù)序列A，找出i,j 使得那一段

14、連續(xù)數(shù)之和最大。 第一行為n第二行為數(shù)列 輸入樣例 6 3 -5 2 4 -1 6 輸出樣例 11 分析： 設(shè)Fi表示Ai為最后一個(gè)元素的最大連續(xù)子序列?？傻梅匠蹋?Fi=max Fi-1,0+Ai時(shí)間復(fù)雜度為O（n）Program zuidalianxuzixulie;var a,s:array 0.10000 of integer; i,j,n,max:integer;begin max:=0; assign(input,lxzxl.txt); reset(input); readln(n); fillchar(s,sizeof(s),0); for i:=1 to n do begin

15、read(ai); si:=si-1 + ai; end; close(input); for i:=1 to n do for j:=1 to n do if sj - si max then max := sj - si; writeln(max);end. 四、街道問題在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。分析這是一道簡(jiǎn)單而又典型的動(dòng)態(tài)規(guī)劃題，許多介紹動(dòng)態(tài)規(guī)劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：按照?qǐng)D中的虛線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點(diǎn)。這時(shí)的模型實(shí)際上已經(jīng)轉(zhuǎn)化成了一個(gè)特殊的多段圖。用決策

16、變量uk=0表示向右走，uk=1表示向上走，則狀態(tài)轉(zhuǎn)移方程如下：(這里的row是地圖豎直方向的行數(shù)）我們看到，這個(gè)狀態(tài)轉(zhuǎn)移方程需要根據(jù)k的取值分兩種情況討論，顯得非常麻煩。相應(yīng)的，把它代入規(guī)劃方程而付諸實(shí)現(xiàn)時(shí)，算法也很繁。因而我們?cè)趯?shí)現(xiàn)時(shí)，一般是不會(huì)這么做的，而代之以下面方法：（這里Distance表示相鄰兩點(diǎn)間的邊長(zhǎng)）這樣做確實(shí)要比上面的方法簡(jiǎn)單多了，但是它已經(jīng)破壞了動(dòng)態(tài)規(guī)劃的本來面目，而不存在明確的階段特征了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那么它的狀態(tài)轉(zhuǎn)移就不全是在兩個(gè)階段之間進(jìn)行的了。也許這沒什么大不了的，因?yàn)閷?shí)踐比理論更有說服力。但是，如果我們把題目擴(kuò)展

17、一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，并且要求兩條路徑的總長(zhǎng)度最短。這時(shí)，再用這種簡(jiǎn)單的方法就不太好辦了。如果非得套用這種方法的話，則最優(yōu)指標(biāo)函數(shù)就需要有四維的下標(biāo)，并且難以處理兩條路徑不能重疊的問題。而我們回到原先標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃法，就會(huì)發(fā)現(xiàn)這個(gè)問題很好解決，只需要加一維狀態(tài)變量就成了。即用xk=(ak,bk)分別表示兩條路徑走到階段k時(shí)所處的位置，相應(yīng)的，決策變量也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態(tài)轉(zhuǎn)移時(shí)將兩條路徑分別考慮在寫規(guī)劃方程時(shí)，只要對(duì)兩條路徑走到同一個(gè)點(diǎn)的情況稍微處理一下，減少可選的決策個(gè)數(shù)：從這個(gè)例子可以看出

18、，合理地劃分階段和選擇狀態(tài)可以給解題帶來方便。 六、花店櫥窗假設(shè)你想以最美觀的方式布置花店的櫥窗。現(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ù)決定了花束在花瓶中的順序，如果IJ，則令花束I必須放在花束J左邊的花瓶中。 例如，假設(shè)一束杜鵑花的標(biāo)識(shí)數(shù)為1，一束秋海棠的標(biāo)識(shí)數(shù)為2，一束康乃馨的標(biāo)識(shí)數(shù)為3，所有的花束在放入花瓶時(shí)必須保持其標(biāo)識(shí)數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠

19、必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個(gè)花瓶中只能放一束花。 每一個(gè)花瓶都具有各自的特點(diǎn)。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個(gè)整數(shù)）來表示，空置花瓶的美學(xué)值為零。在上述例子中，花瓶與花束的不同搭配所具有的美學(xué)值，如下表所示。 花 瓶 1 2 3 4 5 1 (杜鵑花) 7 23 -5 -24 16 2 (秋海棠) 5 21 -4 10 23 3 (康乃馨) -21 5 -4 -20 20 例如，根據(jù)上表，杜鵑花放在花瓶2中，會(huì)顯得非常好看；但若放在花瓶4中則顯得十分難看。 為取得最佳美學(xué)效果，你必須在保持花束順

20、序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。（2）假設(shè)條件 1F100，其中F為花束的數(shù)量，花束編號(hào)從1至F。 FV100，其中V是花瓶的數(shù)量。 -50Aij50，其中Aij是花束i在花瓶j中的美學(xué)值。 （3）輸入 第一行包含兩個(gè)數(shù)：F，V。 隨后的F行中，每行包含V個(gè)整數(shù)，Aij 即為輸入文件中第（i+1 ）行中的第j個(gè)數(shù)。 （4）輸出一行是程序所產(chǎn)生擺放方式的美學(xué)值。【樣例輸入1】 【樣例輸入2】 3 5 7 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 2

21、0 【樣例輸出1】 【樣例輸出2】 53 本題雖然是IOI99中較為簡(jiǎn)單的一題，但其中大有文章可作。說它簡(jiǎn)單，是因?yàn)樗行?，因此我們一眼便可看出這題應(yīng)該用動(dòng)態(tài)規(guī)劃來解決。但是，如何動(dòng)態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？以花束的編號(hào)來劃分階段。在這里，第k階段布置第k束花，共有F束花，有F+1個(gè)階段，增加第F+1階段是為了計(jì)算的方便；狀態(tài)變量xk表示第k束花所在的花瓶。而對(duì)于每一個(gè)狀態(tài)xk，決策uk就是第k+1束花放置的花瓶號(hào)；最優(yōu)指標(biāo)函數(shù)fk(xk)表示從第k束花到第n束花所得到的最大美學(xué)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。狀態(tài)轉(zhuǎn)移方程為 規(guī)劃方程為

22、邊界條件為： ,事實(shí)上這是一個(gè)虛擬的邊界。最后要求的最大美學(xué)價(jià)值是方法1的規(guī)劃方程中的允許決策空間：xk+1ukV-(F-k)+1 比較麻煩，因此有待改進(jìn)。還是以花束的編號(hào)來劃分階段，第k階段布置第k束花；狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k-1束花所在的花瓶；最優(yōu)指標(biāo)fk(xk)表示從第一束花到第k束花所獲得的美學(xué)價(jià)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。則狀態(tài)轉(zhuǎn)移方程為：規(guī)劃方程為：增加的虛擬邊界條件為：最后要求的最大美學(xué)價(jià)值是：可以看出，這種方法實(shí)質(zhì)上和方法1沒有區(qū)

23、別，但是允許決策空間的表示變得簡(jiǎn)單了。以花瓶的數(shù)目來劃分階段，第k個(gè)階段決定花瓶k中是否放花；狀態(tài)變量xk表示前k個(gè)花瓶中放了多少花；而對(duì)于任意一個(gè)狀態(tài)xk，決策就是第xk束花是否放在第k個(gè)花瓶中，用變量uk=1或0來表示。最優(yōu)指標(biāo)函數(shù)fk(xk)表示前k個(gè)花瓶中插了xk束花，所能取得的最大美學(xué)值。注意，這里仍然是倒過來考慮。狀態(tài)轉(zhuǎn)移方程為規(guī)劃方程為邊界條件為三種不同的方法都成功地解決了問題，只不過因?yàn)殡A段的劃分不同，狀態(tài)的表示不同，決策的選擇有多有少，所以算法的時(shí)間復(fù)雜度也就不同。這個(gè)例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規(guī)劃方法。有

24、時(shí)各種方法所產(chǎn)生的效果是差不多的，但更多的時(shí)候，就像我們的例子一樣，兩種方法會(huì)在某個(gè)方面有些區(qū)別。所以，在用動(dòng)態(tài)規(guī)劃解題的時(shí)候，可以多想一想是否有其它的解法。對(duì)于不同的解法，要注意比較，好的算法好在哪里，差一點(diǎn)的算法差在哪里。從各種不同算法的比較中，我們可以更深刻地領(lǐng)會(huì)動(dòng)態(tài)規(guī)劃的構(gòu)思技巧。七、航線設(shè)置問題描述:美麗的萊茵河畔,每邊都分布著N個(gè)城市,兩邊的城市都是唯一對(duì)應(yīng)的友好城市,現(xiàn)需要在友好城市開通航線以加強(qiáng)往來.但因?yàn)槿R茵河常年大霧,如果開設(shè)的航線發(fā)生交叉現(xiàn)象就有可能出現(xiàn)碰船的現(xiàn)象.現(xiàn)在要求近可能多地開通航線并且使航線不能相交! 假如你是一個(gè)才華橫溢的設(shè)計(jì)師,該如何設(shè)置友好城市間的航線使的

25、航線數(shù)又最大又不相交呢? 分析:此問題可以演化成求最大不下降序列來完成.源程序如下:program dongtai; 動(dòng)態(tài)規(guī)劃之友好城市航線設(shè)置問題var d:array1.1000,1.4 of integer; i,j,k,n,L,p:integer; procedure print(L:integer); 打印結(jié)果 begin writeLn(最多可設(shè)置的航線數(shù)是 : ,k); repeat writeLn(dL,1:4,dL,2:4); 輸出可以設(shè)置航線的友好城市代碼 L:=dL,4 untiL L=0 end;begin writeLn(輸入友好城市對(duì)數(shù): ); readLn(n);

26、 writeLn(輸入友好城市對(duì)（友好城市放在同一行:); 輸入 for i:=1 to n do readLn(di,1,di,2); DI，1表示起點(diǎn)，DI，2表示終點(diǎn) for i:=1 to n do begin di,3:=1; DI，3表示可以設(shè)置的航線條數(shù) di,4:=0 DI，4表示后繼，即下一條航線從哪里開始設(shè)置，為0表示不能設(shè)置下一條航線 end;for i:=n-1 downto 1 do 從倒數(shù)第二個(gè)城市開始規(guī)劃 begin L:=0; p:=0; L表示本城市后面可以設(shè)置的航線數(shù)，P表示下條航線從哪個(gè)城市開始 for j:=i+1 to n do 找出本城市后面可以設(shè)置

27、的最大航線數(shù)和小條航線到底從哪個(gè)城市開始設(shè)置 if (di,2 L) then 如果本城市I的終點(diǎn)小于后面城市的終點(diǎn)（即不相交） 并且此城市后面可以設(shè)置的航線數(shù)大于L begin L:=dj,3; 那么L等于城市J的可以設(shè)置航線數(shù) p:=j P等于可以設(shè)置下條航線的城市代碼 end; if L0 then 如果本城市后面總共可以設(shè)置的航線數(shù)0則 begin di,3:=L+1; 本城市可以設(shè)置的航線數(shù)在下個(gè)城市可以設(shè)置航線數(shù)的基礎(chǔ)上加1 di,4:=p DI，4等于本城市后續(xù)城市的代碼 end end; k:=d1,3; K為可以設(shè)置最大航線數(shù)，假設(shè)初值為第一個(gè)城市可以設(shè)置的航線數(shù) L:=1;

28、 L為城市代碼，初值為第一個(gè)城市 for i:=2 to n do 找出可以設(shè)置航線的最大值，賦值給K，同時(shí)L記下哪個(gè)可以設(shè)置最大航線數(shù)的城市代碼 if di,3k then begin k:=di,3; L:=i end; for i:=1 to n do 打印結(jié)果，因?yàn)橛锌赡苡卸喾N方案，所以只要哪個(gè)城市可以設(shè)置的航線數(shù)等于最大值K就打印結(jié)果 if di,3=k then print(i)end.八、最長(zhǎng)不降子序列（1）問題描述設(shè)有由n個(gè)不相同的整數(shù)組成的數(shù)列，記為:a(1)、a(2)、a(n)且a(i)a(j) (ij)例如3，18，7，14，10，12，23，41，16，24。若存在i1

29、i2i3 ie 且有a(i1)a(i2) a(ie)則稱為長(zhǎng)度為e的不下降序列。如上例中3，18，23，24就是一個(gè)長(zhǎng)度為4的不下降序列，同時(shí)也有3，7，10，12，16，24長(zhǎng)度為6的不下降序列。程序要求，當(dāng)原數(shù)列給出之后，求出最長(zhǎng)的不下降序列。（2）算法分析根據(jù)動(dòng)態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索。1 對(duì)a(n)來說，由于它是最后一個(gè)數(shù)，所以當(dāng)從a(n)開始查找時(shí)，只存在長(zhǎng)度為1的不下降序列；2 若從a(n-1)開始查找，則存在下面的兩種可能性：若a(n-1)a(n)則存在長(zhǎng)度為1的不下降序列a(n-1)或a(n)。3 一般若從a(i)開始，此時(shí)最長(zhǎng)不下降序列應(yīng)該按下列方法求出:在a(i+1)

30、,a(i+2),a(n)中，找出一個(gè)比a(i)大的且最長(zhǎng)的不下降序列，作為它的后繼。4.用數(shù)組b(i),c(i)分別記錄點(diǎn)i到n的最長(zhǎng)的不降子序列的長(zhǎng)度和點(diǎn)i后繼接點(diǎn)的編號(hào)(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array1.maxn of integer; fname:string; f:text; n,i,j,max,p:integer;begin readln(fname); assign(f,fname); reset(f); readln(f,n);+ for i:=1 to n do begin read(f,ai);

31、bn:=1; cn:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end; max:=0;p:=0; for i:=1 to n do if bimax then begin max:=bi;p:=i end; writeln(maxlong=,max); write(result is:); while p0 do begin write(ap:5

32、);p:=cp end;end.九、 背包問題背包問題有三種1.部分背包問題 一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n種物品，它們的總重量分別是W1，W2，.,Wn,它們的總價(jià)值分別為C1,C2,.,Cn.求旅行者能獲得最大總價(jià)值。 解決問題的方法是貪心算法:將C1/W1,C2/W2,.Cn/Wn,從大到小排序,不停地選擇價(jià)值與重量比最大的放人背包直到放滿為止. 2.0/1背包 一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，.,Wn,它們的價(jià)值分別為C1,C2,.,Cn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。 分析說明: 顯然這個(gè)題可用深度優(yōu)先方

33、法對(duì)每件物品進(jìn)行枚舉(選或不選用0,1控制). 程序簡(jiǎn)單,但是當(dāng)n的值很大的時(shí)候不能滿足時(shí)間要求，時(shí)間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數(shù) 設(shè) f(i，x)表示前i件物品，總重量不超過x的最優(yōu)價(jià)值 則 f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x） f（n，m）即為最優(yōu)解，邊界條件為f（0，x）0 ，f(i,0)=0; 動(dòng)態(tài)規(guī)劃方法(順推法)程序如下: 程序如下： program knapsack02; const maxm=200;maxn=30; type ar=array1.maxn of integer; var m,n,j,i:integer; c,w:ar; f:array0.maxn,0.maxm of integer; function max(x,y:integer):integer; begin if xy then max