《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃實例分析及程序?qū)崿F(xiàn).doc》由會員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃實例分析及程序?qū)崿F(xiàn).doc（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 動態(tài)規(guī)劃實例分析及程序?qū)崿F(xiàn) 一、數(shù)字三角形 　?。▓D３.１－１）示出了一個數(shù)字三角形。 請編一個程序計算從頂至底的某處的一條路 徑，使該路徑所經(jīng)過的數(shù)字的總和最大。 　●每一步可沿左斜線向下或右斜線向下走； 　●1＜三角形行數(shù)≤100； 　●三角形中的數(shù)字為整數(shù)0，1，…99； 輸入數(shù)據(jù)： 由INPUT.TXT文件中首先讀到的是三角形的行數(shù)。 在例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 輸出數(shù)據(jù)： 把最大總和（整數(shù)）寫入OUTPUT.TXT文件。 上例為： 30 　　　　　　　　　　　　　　　　７ 　　　　　　　　　　　　　　?。场。? 　　　　　　　　　　　　　?。浮。薄。? 　　　　　　　　　　　　　２?。贰。础。? 　　　　　　　　　　　?。础。怠。病。丁。? 　　　　　　　　　　　　　　　（圖３.１－１） 　　　　　　　　　　　 　二、算法分析 　　只要對該題稍加分析，就可以得出一個結(jié)論： 　　如果得到一條由頂至底的某處的一條最佳路徑，那么對于該路徑上的每一個中間點來說，由頂至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此該題是一個典型的多階段決策最優(yōu)化 的問題。 　　我們采用動態(tài)規(guī)劃中的順推解法。按三角形的行劃分階段。若行數(shù)為n, 則可把問題看作一個n-1個階段的決策問題。從始點出發(fā)，依順向求出第一階段、第二階段，……，第n-1階段中各決策點至始點的最佳路徑，最終求出始點到終點的最佳路徑。 　　設(shè)： 　　ｆk（Ｕk）━━從第ｋ階段中的點Ｕk至三角形頂點有一條最佳路徑， 該路徑所經(jīng)過的 數(shù)字的總和最大，ｆk（Ｕk）表示為這個數(shù)字和； 　　由于每一次決策有兩個選擇，或沿左斜線向下，或沿右斜線向下，因此設(shè) 　　Ｕk1━━ｋ－１階段中某點Ｕk沿左斜線向下的點； 　　Ｕk2━━ｋ－１階段中某點Ｕk沿右斜線向下的點； 　?。鋕（Ｕk1）━━ｋ階段中Ｕk1的數(shù)字； 　?。鋕（Ｕk2）━━ｋ階段中Ｕk2的數(shù)字； 　　因而可寫出順推關(guān)系式 　?。鎘（Ｕk）＝ｍａｘ｛ｆk-1（Ｕk）＋ｄk（Ｕk1），ｆk-1（Ｕk）＋ｄk（Ｕk2）｝ 　?。?（Ｕ0）＝０； 　　　　　?。耍剑保?，３，４，……ｎ 　　經(jīng)過一次順推，便可分別求出由頂至底Ｎ個數(shù)的Ｎ條路徑，在這Ｎ條路徑所經(jīng)過的Ｎ個 數(shù)字和中，最大值即為正確答案。 　　　　　　　　　　　　 三、程序分析 　　根據(jù)上述順推關(guān)系，我們編寫程序如下： Program ID1P1; Const Maxn = 100; Type Node = Record Val, Tot : Integer { 當前格數(shù)字; 從[1,1]到當前格的路徑所經(jīng)過的數(shù)字和 } End; Var List : Array [1..Maxn, 1..Maxn] of Node; { 計算表 } N, Max, { 行數(shù), 最大總和 } I, J : Integer; { 輔助變量 } Fi : Text; { 文件變量 } Procedure Init; Begin Assign(Fi, INPUT.TXT); { 文件名和文件變量連接 } Reset(Fi); { 文件讀準備 } Readln(Fi, N); { 讀三角形行數(shù) } For i := 1 to N Do { 讀入三角形各格的數(shù)字 } For j := 1 to i Do Read(Fi, List[i, j].Val); Close(Fi) End;　{init} Procedure Main; Begin List[1, 1].Tot := List[1, 1].Val; { 從[1,1]位置開始往下順推 } For i := 2 to N Do For j := 1 to i Do Begin List[i, j].Tot := -1; { 從[1,1]至[i,j]的數(shù)字和初始化 } If (j <> 1) And (List[i - 1, j - 1].Tot + List[i, j].Val > List[i, j].Tot) Then List[i, j].Tot := List[i - 1, j - 1].Tot + List[i, j].Val; { 若從[i-1,j-1]選擇右斜線向下會使[1,1]至[i,j]的數(shù)字和最大,則決策該步 } If (j <> i) And (List[i - 1, j].Tot + List[i, j].Val > List[i, j].Tot) Then List[i, j].Tot := List[i - 1, j].Tot + List[i, j].Val { 若從[i-1,j]選擇左斜線向下會使[1,1]至[i,j]的數(shù)字和最大,則決策該步 } End; {for} Max := 1; { [1,1]至底行各點的N條路徑所經(jīng)過的數(shù)字和中,選擇最大的一個輸出 } For i := 2 to N Do If List[N, i].Tot > List[N, Max].Tot Then Max := i; Writeln(List[N, Max].Tot) { 輸出最大總和 } End; {main} Begin Init; { 讀入數(shù)字三角形 } Main { 求最大總和 } End.{main} 二、Problem : 打鼴鼠 Contents: 有個n*n個格子，在m個時間點上的不定格子里有數(shù)量不等的鼴鼠出現(xiàn)，機器人每次只能向前后左右移動一個格子，問最多機器人能打多少鼴鼠？ (n<=1000, m<=10000) Type: 動態(tài)規(guī)劃 Difficulty: 2 Source: HNOIxx_day_*_* Solution : a) 記得學(xué)OI不到幾個月，高一剛上來就做的這道題..著實郁悶了半天,有一個思路是開1000*1000 的數(shù)組亂搞…忘了可以過幾個來著.. b) 又翻到這道題的時候是2月份了..發(fā)現(xiàn) f[i]表示：如果機器人最后打死的老鼠是第i只，這種情況下機器人最多可以打死多少老鼠。就可以了,然后我赫然發(fā)現(xiàn)10^8 div 2次的若干基本操作是要TLE的 c) 鑒于這道題郁悶的理論時間復(fù)雜度無法優(yōu)化，我請教了朱老師，原來動態(tài)規(guī)劃枚舉順序也有其優(yōu)化技巧，由于思路不是自己的，僅作簡要介紹： a) (1).將更快、更容易“短路”的判斷放在前面 b) (2).將內(nèi)部循環(huán)（j的循環(huán)）倒序，逼近最優(yōu)解 d) 我的計算機有點慢… 總分 = 100.0 第一題：mole 得分 = 100.0 用時 = 7.16s mole-0(mole1.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 0.01s 空間 = 0.71M mole-1(mole2.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 0.01s 空間 = 0.71M mole-2(mole3.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 0.02s 空間 = 0.71M mole-3(mole4.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 0.98s 空間 = 0.71M mole-4(mole5.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.02s 空間 = 0.71M mole-5(mole6.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.00s 空間 = 0.71M mole-6(mole7.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.05s 空間 = 0.71M mole-7(mole8.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.02s 空間 = 0.71M mole-8(mole9.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.02s 空間 = 0.71M mole-9(mole10.In) 結(jié)果 = 正確 得分 = 10.0 用時 = 1.02s 空間 = 0.71M [分析] 設(shè)第i只老鼠在第Ti個時刻出現(xiàn)在(xi, yi)，T1<=T2<=T3<=…<=Tm。 假設(shè)機器人打死了L只老鼠，不妨設(shè)這些老鼠的編號是a1, a2, …, aL。顯然對于任意的i(1<=i<=L-1)都有T[ai+1]-T[ai]>=|x[ai+1]-x[ai]|+|y[ai+1]-y[ai]|。 f[i]表示：如果機器人最后打死的老鼠是第i只，這種情況下機器人最多可以打死多少老鼠。 可以列出方程： f[i] = max{f[j]+1, 1} 1<=j=|xi-xj|+|yi-yj| 最后求的答案就是max{f[i]}(1<=i<=m) 此算法時間復(fù)雜度為O(m2)?？紤]到m<=10000，而時限只有1second，所以還必須進行一些代碼優(yōu)化。 因為j f[i]) then f[i] := f[j]; f[i]:=f[i]+1; end; 它無疑是正確的。但是循環(huán)中的判斷語句大有文章可做：上面的代碼每次都鐵定至少要執(zhí)行3次減法、2次絕對值、1次比較運算。這無疑是極度昂貴的操作代價。所以我們可以將(f[j]>f[i])這個比較“便宜”的判斷條件提到前面，變成如下形式： if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then 這樣做的好處是一旦f[j]<=f[i]就可以執(zhí)行“短路操作”（也就是說后面那一大截速度很慢的操作都可以避免。不過編譯的時候一定要記得設(shè)成{$B+}） 實踐證明速度是快了不少?？墒菍τ?second的時限還是不能勝任。實戰(zhàn)游戲經(jīng)驗告訴我們，機器人一般情況下不可能打完一只老鼠之后就跑到很遠的地方去尋找新的獵物，肯定是一路上碰到一點老鼠就打一點。所以機器人相繼打的兩只老鼠的出現(xiàn)時間不可能相差太遠。因此在方程 f[i] = max{f[j]+1, 1} 1<=j=|xi-xj|+|yi-yj| 之中，使得i達到最優(yōu)的j肯定不會和i差得太遠。 同時在我們的判斷語句中： if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then f[i]越早接近最優(yōu)值，判斷語句的效率就越高（因為后面一截可以被短路掉）。因此我們將循環(huán)語句改成這樣的形式： for i := 1 to m do begin f[i] := 0; for j := i – 1 downto 1 do if (f[j]>f[i]) and (abs(x[i]-x[j]) + abs(y[i]-y[j])<=T[i]-T[j]) then f[i] := f[j]; f[i]:=f[i]+1; end; 實踐發(fā)現(xiàn)，最慢的數(shù)據(jù)大概0.7s即可出解。 至此問題解決了。 Program mole; {$B+} var f,t,x,y: array [1..10000] of longint; i,j,m,n,ans: longint; begin assign(input,mole.in); reset(input); readln(n,m); for i:= 1 to m do readln(t[i],x[i],y[i]); close(input); fillchar(f,sizeof(f),0); for i:= 1 to m do begin for j:= i-1 downto 1 do if (f[j]>f[i]) and (abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) then f[i]:=f[j]; inc(f[i]); if f[i]>ans then ans:=f[i]; end; assign(output,mole.out); rewrite(output); writeln(ans); close(output); END. 三、最大連續(xù)子序列 給出一個長度為n 的整數(shù)序列A，找出i,j 使得那一段連續(xù)數(shù)之和最大。 第一行為n第二行為數(shù)列 輸入樣例 6 3 -5 2 4 -1 6 輸出樣例 11 [分析]： 設(shè)Fi表示Ai為最后一個元素的最大連續(xù)子序列。可得方程： Fi=max {Fi-1,0}+Ai 時間復(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 read(a[i]); s[i]:=s[i-1] + a[i]; end; close(input); for i:=1 to n do for j:=1 to n do if s[j] - s[i] > max then max := s[j] - s[i]; writeln(max); end. 四、街道問題 在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。 [分析] 這是一道簡單而又典型的動態(tài)規(guī)劃題，許多介紹動態(tài)規(guī)劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的： 按照圖中的虛線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當前處于這一階段上的哪一點。這時的模型實際上已經(jīng)轉(zhuǎn)化成了一個特殊的多段圖。用決策變量uk=0表示向右走，uk=1表示向上走，則狀態(tài)轉(zhuǎn)移方程如下： (這里的row是地圖豎直方向的行數(shù)） 我們看到，這個狀態(tài)轉(zhuǎn)移方程需要根據(jù)k的取值分兩種情況討論，顯得非常麻煩。相應(yīng)的，把它代入規(guī)劃方程而付諸實現(xiàn)時，算法也很繁。因而我們在實現(xiàn)時，一般是不會這么做的，而代之以下面方法： （這里Distance表示相鄰兩點間的邊長） 這樣做確實要比上面的方法簡單多了，但是它已經(jīng)破壞了動態(tài)規(guī)劃的本來面目，而不存在明確的階段特征了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那么它的"狀態(tài)轉(zhuǎn)移"就不全是在兩個階段之間進行的了。 也許這沒什么大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，并且要求兩條路徑的總長度最短。這時，再用這種"簡單"的方法就不太好辦了。 如果非得套用這種方法的話，則最優(yōu)指標函數(shù)就需要有四維的下標，并且難以處理兩條路徑"不能重疊"的問題。 而我們回到原先"標準"的動態(tài)規(guī)劃法，就會發(fā)現(xiàn)這個問題很好解決，只需要加一維狀態(tài)變量就成了。即用xk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應(yīng)的，決策變量也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態(tài)轉(zhuǎn)移時將兩條路徑分別考慮 在寫規(guī)劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數(shù)： 從這個例子可以看出，合理地劃分階段和選擇狀態(tài)可以給解題帶來方便。 六、花店櫥窗 假設(shè)你想以最美觀的方式布置花店的櫥窗?，F(xiàn)在你有F束不同品種的花束，同時你也有至少同樣數(shù)量的花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從1至V順序編號，V是花瓶的數(shù)目，從左至右排列，則最左邊的是花瓶1，最右邊的是花瓶V。花束可以移動，并且每束花用1至F間的整數(shù)唯一標識。標識花束的整數(shù)決定了花束在花瓶中的順序，如果I＜J，則令花束I必須放在花束J左邊的花瓶中。 例如，假設(shè)一束杜鵑花的標識數(shù)為1，一束秋海棠的標識數(shù)為2，一束康乃馨的標識數(shù)為3，所有的花束在放入花瓶時必須保持其標識數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個花瓶中只能放一束花。 每一個花瓶都具有各自的特點。因此，當各個花瓶中放入不同的花束時，會產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個整數(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中，會顯得非常好看；但若放在花瓶4中則顯得十分難看。 為取得最佳美學(xué)效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。 （2）假設(shè)條件 1≤F≤100，其中F為花束的數(shù)量，花束編號從1至F。 F≤V≤100，其中V是花瓶的數(shù)量。 -50≤Aij≤50，其中Aij是花束i在花瓶j中的美學(xué)值。 （3）輸入 第一行包含兩個數(shù)：F，V。 隨后的F行中，每行包含V個整數(shù)，Aij 即為輸入文件中第（i+1 ）行中的第j個數(shù)。 （4）輸出 一行是程序所產(chǎn)生擺放方式的美學(xué)值。 【樣例輸入1】 【樣例輸入2】 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20 【樣例輸出1】 【樣例輸出2】 53 本題雖然是IOI’99中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應(yīng)該用動態(tài)規(guī)劃來解決。但是，如何動態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？ <方法1> 以花束的編號來劃分階段。在這里，第k階段布置第k束花，共有F束花，有F+1個階段，增加第F+1階段是為了計算的方便；狀態(tài)變量xk表示第k束花所在的花瓶。而對于每一個狀態(tài)xk，決策uk就是第k+1束花放置的花瓶號；最優(yōu)指標函數(shù)fk(xk)表示從第k束花到第n束花所得到的最大美學(xué)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。 狀態(tài)轉(zhuǎn)移方程為 規(guī)劃方程為 邊界條件為： , 事實上這是一個虛擬的邊界。 最后要求的最大美學(xué)價值是 <方法2> 方法1的規(guī)劃方程中的允許決策空間：xk+1≤uk≤V-(F-k)+1 比較麻煩，因此有待改進。還是以花束的編號來劃分階段，第k階段布置第k束花；狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k-1束花所在的花瓶；最優(yōu)指標fk(xk)表示從第一束花到第k束花所獲得的美學(xué)價值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。則狀態(tài)轉(zhuǎn)移方程為： 規(guī)劃方程為： 增加的虛擬邊界條件為： 最后要求的最大美學(xué)價值是： 可以看出，這種方法實質(zhì)上和方法1沒有區(qū)別，但是允許決策空間的表示變得簡單了。 <方法3> 以花瓶的數(shù)目來劃分階段，第k個階段決定花瓶k中是否放花；狀態(tài)變量xk表示前k個花瓶中放了多少花；而對于任意一個狀態(tài)xk，決策就是第xk束花是否放在第k個花瓶中，用變量uk=1或0來表示。最優(yōu)指標函數(shù)fk(xk)表示前k個花瓶中插了xk束花，所能取得的最大美學(xué)值。注意，這里仍然是倒過來考慮。 狀態(tài)轉(zhuǎn)移方程為 規(guī)劃方程為 邊界條件為 三種不同的方法都成功地解決了問題，只不過因為階段的劃分不同，狀態(tài)的表示不同，決策的選擇有多有少，所以算法的時間復(fù)雜度也就不同。 這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規(guī)劃方法。有時各種方法所產(chǎn)生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區(qū)別。所以，在用動態(tài)規(guī)劃解題的時候，可以多想一想是否有其它的解法。對于不同的解法，要注意比較，好的算法好在哪里，差一點的算法差在哪里。從各種不同算法的比較中，我們可以更深刻地領(lǐng)會動態(tài)規(guī)劃的構(gòu)思技巧。 七、航線設(shè)置 問題描述:美麗的萊茵河畔,每邊都分布著N個城市,兩邊的城市都是唯一對應(yīng)的友好城市,現(xiàn)需要在友好城市開通航線以加強往來.但因為萊茵河常年大霧,如果開設(shè)的航線發(fā)生交叉現(xiàn)象就有可能出現(xiàn)碰船的現(xiàn)象.現(xiàn)在要求近可能多地開通航線并且使航線不能相交! 假如你是一個才華橫溢的設(shè)計師,該如何設(shè)置友好城市間的航線使的航線數(shù)又最大又不相交呢? 分析:此問題可以演化成求最大不下降序列來完成.源程序如下: program dongtai; {動態(tài)規(guī)劃之友好城市航線設(shè)置問題} var d:array[1..1000,1..4] of integer; i,j,k,n,L,p:integer; procedure print(L:integer); {打印結(jié)果} begin writeLn(最多可設(shè)置的航線數(shù)是 : ,k); repeat writeLn(d[L,1]:4,d[L,2]:4); {輸出可以設(shè)置航線的友好城市代碼} L:=d[L,4] untiL L=0 end; begin writeLn(輸入友好城市對數(shù): ); readLn(n); writeLn(輸入友好城市對（友好城市放在同一行:); {輸入} for i:=1 to n do readLn(d[i,1],d[i,2]); {D[I，1]表示起點，D[I，2]表示終點} for i:=1 to n do begin d[i,3]:=1; {D[I，3]表示可以設(shè)置的航線條數(shù)} d[i,4]:=0 {D[I，4]表示后繼，即下一條航線從哪里開始設(shè)置，為0表示不能設(shè)置下一條航線} end; for i:=n-1 downto 1 do {從倒數(shù)第二個城市開始規(guī)劃} begin L:=0; p:=0; {L表示本城市后面可以設(shè)置的航線數(shù)，P表示下條航線從哪個城市開始} for j:=i+1 to n do {找出本城市后面可以設(shè)置的最大航線數(shù)和小條航線到底從哪個城市開始設(shè)置} if (d[i,2] L) then {如果本城市I的終點小于后面城市的終點（即不相交）} {并且此城市后面可以設(shè)置的航線數(shù)大于L} begin L:=d[j,3]; {那么L等于城市J的可以設(shè)置航線數(shù)} p:=j {P等于可以設(shè)置下條航線的城市代碼} end; if L>0 then {如果本城市后面總共可以設(shè)置的航線數(shù)>0則} begin d[i,3]:=L+1; {本城市可以設(shè)置的航線數(shù)在下個城市可以設(shè)置航線數(shù)的基礎(chǔ)上加1} d[i,4]:=p {D[I，4]等于本城市后續(xù)城市的代碼} end end; k:=d[1,3]; {K為可以設(shè)置最大航線數(shù)，假設(shè)初值為第一個城市可以設(shè)置的航線數(shù)} L:=1; {L為城市代碼，初值為第一個城市} for i:=2 to n do {找出可以設(shè)置航線的最大值，賦值給K，同時L記下哪個可以設(shè)置最大航線數(shù)的城市代碼} if d[i,3]>k then begin k:=d[i,3]; L:=i end; for i:=1 to n do {打印結(jié)果，因為有可能有多種方案，所以只要哪個城市可以設(shè)置的航線數(shù)等于最大值K就打印結(jié)果} if d[i,3]=k then print(i) end. 八、最長不降子序列 （1）問題描述 設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為: a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 例如3，18，7，14，10，12，23，41，16，24。 若存在i1a(n)則存在長度為1的不下降序列a(n-1)或a(n)。 3 一般若從a(i)開始，此時最長不下降序列應(yīng)該按下列方法求出: 在a(i+1),a(i+2),…,a(n)中，找出一個比a(i)大的且最長的不下降序列，作為它的后繼。 4.用數(shù)組b(i),c(i)分別記錄點i到n的最長的不降子序列的長度和點i后繼接點的編號 (3) 程序如下:（逆推法） program li1; const maxn=100; var a,b,c:array[1..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,a[i]); b[n]:=1; c[n]:=0; end; for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (a[i]max) then begin max:=b[j];p:=j end; if p<>0 then begin b[i]:=b[p]+1;c[i]:=p end end; max:=0;p:=0; for i:=1 to n do if b[i]>max then begin max:=b[i];p:=i end; writeln(maxlong=,max); write(result is:); while p<>0 do begin write(a[p]:5);p:=c[p] end; end. 九、 背包問題 背包問題有三種 1.部分背包問題　 一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n種物品，它們的總重量分別是W1，W2，...,Wn,它們的總價值分別為C1,C2,...,Cn.求旅行者能獲得最大總價值。 解決問題的方法是貪心算法:將C1/W1,C2/W2,...Cn/Wn,從大到小排序,不停地選擇價值與重量比最大的放人背包直到放滿為止. 2.0/1背包 一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，...,Wn,它們的價值分別為C1,C2,...,Cn.若每種物品只有一件求旅行者能獲得最大總價值。 <1>分析說明: 顯然這個題可用深度優(yōu)先方法對每件物品進行枚舉(選或不選用0,1控制). 程序簡單,但是當n的值很大的時候不能滿足時間要求，時間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數(shù) 設(shè) f(i，x)表示前i件物品，總重量不超過x的最優(yōu)價值 則 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x）） f（n，m）即為最優(yōu)解，邊界條件為f（0，x）＝0 ，f(i,0)=0; 動態(tài)規(guī)劃方法(順推法)程序如下: 程序如下： program knapsack02; const maxm=200;maxn=30; type ar=array[1..maxn] of integer; var m,n,j,i:integer; c,w:ar; f:array[0..maxn,0..maxm] of integer; function max(x,y:integer):integer; begin if x>y then max:=x else max:=y; end; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else f[i,j]:=f[i-1,j]; end; writeln(f[n,m]); end. 使用二維數(shù)組存儲各子問題時方便，但當maxm較大時如maxn=xx時不能定義二維數(shù)組f,怎么辦,其實可以用一維數(shù)組,但是上述中j:=1 to m 要改為j:=m downto 1,為什么?請大家自己解決。 3.完全背包問題 一個旅行者有一個最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，...,Wn, 每件的價值分別為C1,C2,...,Cn.若的每種物品的件數(shù)足夠多. 求旅行者能獲得的最大總價值。 本問題的數(shù)學(xué)模型如下： 設(shè) f(x)表示重量不超過x公斤的最大價值， 則 f(x）=max{f(x-w[i])+c[i]} 當x>=w[i] 1<=i<=n 程序如下:（順推法） program knapsack04; const maxm=xx;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; f:array[0..maxm] of integer; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); f(0):=0; for i:=1 to m do for j:=1 to n do begin if i>=w[j] then t:=f[i-w[j]]+c[j]; if t>f[i] then f[i]:=t end; writeln(f[m]); end. 十、 最短路徑 　 問題描述： 如圖：求v1到v10的最短路徑長度及最短路徑。 　 圖的鄰接矩陣如下： 0 2 5 1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 12 14 -1 -1 -1 -1 -1 -1 0 -1 6 10 4 -1 -1 -1 -1 -1 -1 0 13 12 11 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 3 9 -1 -1 -1 -1 -1 -1 0 -1 6 5 -1 -1 -1 -1 -1 -1 -1 0 -1 10 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 0 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 采用逆推法 設(shè)f（x）表示點x到v10的最短路徑長度 則 f(10)=0 f(x)=min{ f(i)+a[x,i] 當a[x,i]>0 ,x0) and (b[j]<>maxint) and (b[j]+a[i,j]0 do begin write(x:5); x:=c[x]; end; end.