【正文】 L,k,max:longint。 rewrite(output)。 until (x=0) and (y=0)。 //保存從第 i個地窖起能挖到最大地雷數(shù) f[i,2]:=k。39。 end. 【 例 8】 輪船問題 () 【 問題描述 】 某國家被一條河劃分為南北兩部分，在南岸和北岸總共有 N對城市，每一城市在對岸都有唯一的友好城市，任何兩個城市都沒有相同的友好城市。在河的同一邊，任何兩個城市的位置都是不同的。 于是，我們從上面的分析中再深入，將航線按起點坐標(biāo)排好序后，如上所述，在本題中，只要線 J的起點小于線 I的起點，同時它的終點也小于線 I的終點，則線J和線 I不相交。在棋盤上任一點有一個中國象棋馬， 馬走的規(guī)則為： 。 從 (x1， y1)出發(fā)，按照由左而右的順序定義階段的方向。 n[n[0]+1]=total│total=n[j]+k*num[i]， h[total]=false， 1≤i≤6， 1≤j≤n[0]， 1≤k≤a[i] 階段 i： 分析第 i種砝碼 (１ ≤i≤6)； 狀態(tài) j：枚舉現(xiàn)有的不同重量（１ ≤j≤n[0]）； 決策 k：在現(xiàn)有重量的基礎(chǔ)上放 k塊第 i種砝碼，產(chǎn)生重量 n[j]+k*num[i](１ ≤k≤a[i])； 計算過程如下： fillchar(h,sizeof(h),false)。 end。設(shè)狀態(tài)轉(zhuǎn)移方程 f[i， j]——在前 i個物品中選擇若干個物品（必須包括物品 i）裝箱，其體積正好為 j的標(biāo)志。 //裝箱前，狀態(tài)轉(zhuǎn)移方程初始化 f0[0]:=true。顯然最小剩余空間為 vk: for k:=v downto 0 do //按照遞減順序枚舉所有可能的體積 if f1[k] then begin //若箱子能裝入體積為 i的物品，則輸出剩余空間 vi，并退出程序 writeln(vk)。 【 輸出文件 】 輸出文件 ，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列。 具體算法如下： readln(n)。 for j:=i+1 to n do if (a[j]a[i])and(c[j]+1c[i])then c[i]:=c[j]+1。 【 例題 5】 櫥窗布置（ Flower） 【 問題描述 】 假設(shè)以最美觀的方式布置花店的櫥窗，有 F束花，每束花的品種都不一樣，同時，至少有同樣數(shù)量的花瓶，被按順序擺成一行，花瓶的位置是固定的，并從左到右，從 1到 V順序編號， V是花瓶的數(shù)目。 end。顯然 c[i]={c[j]|同學(xué) j的身高 同學(xué) i的身高 }+1； 由上述狀態(tài)轉(zhuǎn)移方程可知，計算合唱隊形的問題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使 b[i]和 c[i]最大，子問題的解 b[j]和 c[k]必須最大 (1≤j≤i1 ， i+1≤k≤n))和重迭子問題的性質(zhì) (為求得 b[i]和 c[i]，必須一一查閱子問題的解 b[1]‥ b[i1]和c[i+1]‥ c[n])，因此可采用動態(tài)程序設(shè)計的方法求解。 【 輸入文件 】 輸入文件 N（ 2 ≤ N ≤ 100），表示同學(xué)的總數(shù)。 經(jīng)過上述運算，最優(yōu)化問題轉(zhuǎn)化為判定性問題。 for i:=1 to n do readln(x[i])。問題是當(dāng)前階段的剩余空間最小，并不意味下一階段的剩余空間也一定最小，即該問題并不具備最優(yōu)子結(jié)構(gòu)的特征。 inc(n[0])。顯然 我們采用動態(tài)程序設(shè)計的方法計算起點 (x1， y1)至終點（ x2， y2）的路徑數(shù)目 map[x2， y2]： 階段 j：中國象棋馬當(dāng)前的列位置 (y1≤j≤y2)； 狀態(tài) i：中國象棋馬在 j列的行位置（ 1≤i≤n）； 決策 k：中國象棋馬在（ i， j）的起跳方向 (1≤k≤4)； 計算過程如下： fillchar(map， sizeof(map)， 0)； map[x1， y1] ←1 ； //從（ x1， y1）出發(fā) for j←y1 to y2 do // 遞推中國象棋馬的列位置 for i←1 to n do // 遞推中國象棋馬在 j列的行位置 for k←1 to 4 do // 遞推中國象棋馬在（ i， j）的 4個跳動方向 begin 中國象棋馬由（ i， j）出發(fā)，沿著 k方向跳至（ x， y） if (x? ｛１ ..n｝ )∧ (y? {1..y2}) //計算狀態(tài)轉(zhuǎn)移方程 then map[x， y] ←map[i ， j]+map[x， y] end； //for writeln(map[x2， y2]： 0： 0)； //輸出從（ x1， y1）到（ x2， y2）的路徑數(shù)目 【 例題 2】 砝碼稱重 【 問題描述 】 設(shè)有 1g， 2g， 3g， 5g， 10g， 20g的砝碼各若干枚（其總重 ≤1000g），要求： 【 輸入格式 】 a1 a2 a3 a4 a5 a6(表示 1g砝碼有 a1個， 2g砝碼有 a2個， ....20g砝碼有 a6個 ) 【 輸出格式 】 Total=N (N表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況 ) 【 輸入樣例 】 1 1 0 0 0 0 【 輸出樣例 】 Total=3，表示可以稱出 1g， 2g， 3g三種不同的重量 【 算法分析 】 const num： array[1..6] of shortint=(1， 2， 3， 5， 10， 20)； //砝碼的重量序列 var a： array[1..6] of integer； //6種砝碼的個數(shù)｝ h： array[0..1000] of boolean； //重量的訪問標(biāo)志序列｝ n： array[0..1000] of integer； //n[0]—不同重量數(shù)； n[j]—第 j種重量 (１ ≤j≤n[0]) total， i， j， k： integer； //total—目前稱出的重量 我們按照第１種砝碼，第２種砝碼 …… 第６種砝碼的順序分析。本題并不要求每一條路徑的具體走法。這時再來設(shè)計算法，往往能事半功倍。此時剩下的線則全不交叉。第二行是一個整數(shù) N(1=N=5000)，表示分布在河兩岸的城市對數(shù)。 //輸出最多挖出的地雷數(shù) close(input)。 k:=f[k,2]。 end。 repeat readln(x,y)。39。 a:array[1..200,1..200] of boolean。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。 //輸出最短路徑的值 x:=1。 for i:=1 to n do //輸入各個城市之間距離 for j:=1 to n do read(a[i,j])。39。 end. 經(jīng)過計算，其數(shù)據(jù)存儲表如下 I I=1 I=2 I=3 I=4 I=5 I=6 I=7 I=8 A[I] 389 207 155 300 299 170 158 65 B[I] 1 2 3 2 3 4 5 6 N值 1 2 H[1] 389 207 155 65 H[2] 300 299 170 158 【 例 6】 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由 AE。 if x=0 then begin inc(n)。 begin repeat inc(i)。由于利用了二分查找，這種算法的復(fù)雜度為 O(nlogn)，優(yōu)于一般的 O(n^2)。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。,b[k])。 c[i] := k。 end。 階段 i：由右而左計算導(dǎo)彈 n‥ 導(dǎo)彈 1中可攔截的最多導(dǎo)彈數(shù)（ 1≤i≤n）； 狀態(tài) B[i]：由于每個階段中僅一個狀態(tài)，因此可通過一重循環(huán) for i := n1 downto 1 do 枚舉每個階段的狀態(tài) B[i]； 決策 k：在攔截導(dǎo)彈 i之后應(yīng)攔截哪一枚導(dǎo)彈可使得 B[i]最大（ i+1≤k≤n）， 1 2 3 4 5 6 7 8 9 10 11 12 13 14 I 13 7 9 16 38 24 37 18 44 19 21 22 63 15 A[I] //高度 2 1 1 2 4 3 3 2 3 2 2 2 2 1 B[I] //可攔截數(shù) 2 0 0 14 6 8 8 14 10 14 14 14 14 0 C[I] //再攔截 【 參考程序 】 （逆推法） program ex14_4_1。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。,b[k,2])。 if L0 then begin b[i,2]:=L+1。 b[i,2]:=1。 【 參考程序 】 program ex14_3。 b[i,3]:=k。b[i,3]:=0。b(I,2)表示從 I位置到達(dá) N的最長不下降序列長度 3 1Max = 39。 readln。 i,j,n : integer。 窮舉搜索往往是不可能的，當(dāng)層數(shù) N = 100時，路徑條數(shù) P = 299這是一個非常大的數(shù)，即使用世界上最快的電子計算機，也不能在規(guī)定時間內(nèi)計算出來。,a[1,1,2])。 for x:=1 to n do //輸入數(shù)塔的初始值 for y:=1 to x do begin read(a[x,y,1])。 B．自底向上計算：（給出遞推式和終止條件） ①從底層開始，本身數(shù)即為最大數(shù)； ②倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)： 12+6=18， 13+14=27，24+15=39， 24+8=32； ③倒數(shù)第三層的計算，取決于底二層計算的數(shù)據(jù)： 27+12=39， 39+7=46，39+26=65 ④ 倒數(shù)第四層的計算，取決于底三層計算的數(shù)據(jù)： 46+11=57， 65+8=73 ⑤ 最后的路徑： 13——8——26——15——24 C．?dāng)?shù)據(jù)結(jié)構(gòu)及算法設(shè)計 ①圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右 ②用三維數(shù)組表示數(shù)塔： a[x,y,1]表示行、列及結(jié)點本身數(shù)據(jù) ,a[x,y,2]能夠取得最大值 ,a[x,y,3]表示前進(jìn)的方向 ——0向下， 1向右； ③算法： 數(shù)組初始化，輸入每個結(jié)點值及初始的最大路徑、前進(jìn)方向為 0； 從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán) N1次； 從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的值比原先多1則向右，否則向下。因此，我們在遇到這兩類問題時，不妨多聯(lián)系、多發(fā)展，舉一反三，從比較中更深入地理解動態(tài)規(guī)劃的思想。如果用貪心法又往往得不到最優(yōu)解。這種算法就是遞推。 d[4,2,1] := 4。 d[2,2,2] := 8。 f : array[1..5,1..4] of int