【正文】 eger。在劃分階段時(shí)，注意劃分后的階段一定是有序的或者是可排序的，否則問題就無法求解。 動(dòng)態(tài)規(guī)劃的無后效性原則。全過程中各階段決策變量所組成的有序總體稱為策略。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。用 DK（ XI，X+1J）表示在第 K階段由初始狀態(tài) XI到下階段的初始狀態(tài) X+1J的路徑距離，F(xiàn)K（ XI）表示從第 K階段的 XI到終點(diǎn) E的最短距離，利用倒推的方法，求解 A到 E的最短距離。我們也可以通過對若干有代表性的問題的動(dòng)態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會(huì)并掌握這一設(shè)計(jì)方法。因此讀者在學(xué)習(xí)時(shí)，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解?，F(xiàn)在想從城市 A到達(dá)城市 E，怎樣走路程最短？最短路程的長度是多少？ 【 算法分析 】 把 A到 E的全過程分成四個(gè)階段，用 K表示階段變量，第 1階段有一個(gè)初始狀態(tài) A，有兩條可供選擇的支路 AB AB2；第 2階段有兩個(gè)初始狀態(tài) BB2， B1有三條可供選擇的支路， B2有兩條可供選擇的支路 …… 。 2. 狀態(tài)和狀態(tài)變量： 某一階段的出發(fā)位置稱為狀態(tài)，通常一個(gè)階段包含若干狀態(tài)。 4．策略和最優(yōu)策略： 所有階段依次排列構(gòu)成問題的全過程。在例題 1最短路徑問題中， A到 E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn) E的路徑，也必然是該點(diǎn)到終點(diǎn) E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個(gè)局部優(yōu)化。 動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟： 劃分階段 按照問題的時(shí)間或空間特征，把問題劃分為若干個(gè)階段。 【 例 1】 對應(yīng)的 Pascal程序如下： var d : array[1..4,1..4,1..4] of integer。 d[2,1,3] := 3。 d[4,1,1] := 3。 end. 第二節(jié) 動(dòng)態(tài)規(guī)劃與遞推 —— 動(dòng)態(tài)規(guī)劃是最優(yōu)化算法 由于動(dòng)態(tài)規(guī)劃的“名氣”如此之大，以至于很多人甚至一些資料書上都往往把一種與動(dòng)態(tài)規(guī)劃十分相似的算法，當(dāng)作是動(dòng)態(tài)規(guī)劃。 這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如 40），則需要列舉出的路徑條數(shù)將是一個(gè)非常龐大的數(shù)目。 一般說來，很多最優(yōu)化問題都有著對應(yīng)的計(jì)數(shù)問題；反過來，很多計(jì)數(shù)問題也有著對應(yīng)的最優(yōu)化問題。 A．從根結(jié)點(diǎn) 13出發(fā)，選取它的兩個(gè)方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時(shí)，每個(gè)結(jié)點(diǎn)其后繼僅有兩個(gè)結(jié)點(diǎn)，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點(diǎn)開始到底端的最大路徑。 readln(n)。max=39。 writeln(a[n,y,1]) end. 輸入： 5 //數(shù)塔層數(shù) 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11 輸出結(jié)果： max=86 138261524 【 解法二 】 （順推法） 【 算法分析 】 此題貪心法往往得不到最優(yōu)解，例如 1311121413其路徑的值為 63，但這不是最優(yōu)解。 Var a,b : array[1..100,0..100] of word。 for i := 1 to n do //輸入數(shù)塔的初始值 begin for j := 1 to i do read(a[i,j])。 //在第 n行中找出數(shù)塔最大值 writeln(39。 ㈡算法分析： 根據(jù)動(dòng)態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索 (當(dāng)然從前往后也一樣 )。b(I,1)表示第 I個(gè)數(shù)的數(shù)值本身； 2 b[i,2]:=1。 if L0 then begin b[i,2]:=L+1。 end。 for i:=1 to n do //輸入序列的初始值 begin read(b[i,1])。 end。max=39。但是這種攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。為此，我們設(shè)置了一張記憶表 C[i]，在按從后往前方式求解的過程中，將每一個(gè)子問題的最佳決策保存起來，避免在輸出方案時(shí)重復(fù)計(jì)算。 c[n] := 0。 b[i] := max+1。Max = 39。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。最后， b數(shù)組被賦值的元素最大下標(biāo)就是第一問的答案。 i,j,m,n,x,max:integer。 for j:=1 to n do //計(jì)算由哪一套系統(tǒng)攔截導(dǎo)彈 if h[j]=a[i] then if x=0 then x:=j else if h[j]h[x] then x:=j。,n)。 begin assign(input,39。 readln(n)。,f[1])。同時(shí)，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的。 var f:array[1..200,1..2] of longint。 assign(output,39。 readln。 k:=j。write(k)。 writeln(max)。 x表示河的長度而 y表示寬。 第二，將 J數(shù)組從大到小排序，每刪除一條線，則將與之相交的線的 J值減 1，重復(fù)這個(gè)過程，直到所有 J值都為 0。 從以上分析過程可以得出：當(dāng)我們拿到一道題時(shí)，不要急于求解，而應(yīng)先將題目的表面現(xiàn)象一層層象剝竹筍一樣去掉，只留下最實(shí)質(zhì)的內(nèi)容。但問題是搜索效率太低，根本不可能在較短的時(shí)間內(nèi)出解。初始時(shí)，除 map[x1， y1]=1外其余為０。 //產(chǎn)生重量 if not h[total] then //若該重量未產(chǎn)生過，則設(shè)訪問標(biāo)志 begin h[total]:=true。 【 輸入格式 】 箱子的容量 v 物品數(shù) n 接下來 n行，分別表示這 n個(gè)物品的體積 【 輸出格式 】 箱子剩余空間 【 輸入輸出樣例 】 輸入： 24 6 8 3 12 7 9 7 輸出： 0 【 算法分析 】 使用 動(dòng)態(tài)程序設(shè)計(jì)方法計(jì)算箱子的最小剩余空間，如果按照物品序號依次考慮裝箱順序的話，則問題具有明顯的階段特征。我們按照下述方法計(jì)算狀態(tài)轉(zhuǎn)移方程 f1： readln(v,n)。 //記下當(dāng)前裝箱情況 end。 你的任務(wù)是，已知所有 N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。顯然 b[i]={b[j]|同學(xué) j的身高 同學(xué) i的身高 }+1； c為由右而左身高遞增的人數(shù)序列，其中 c[i]為同學(xué) n‥ 同學(xué) i間（包括同學(xué) i）身高滿足遞增順序的最多人數(shù)。 for j:=1 to i1 do if (a[i]a[j])and(b[j]+1b[i]) then b[i]:=b[j]+1。 //輸出出列人數(shù) 這個(gè)算法的時(shí)間復(fù)雜度為 O(n2)，在 1秒時(shí)限內(nèi)可解決 n≤100范圍內(nèi)的問題。 end。 //讀學(xué)生數(shù) for i:=1 to n do read(a[i])。 【 樣例輸入 】 8 186 186 150 200 160 130 197 220 【 樣例輸出 】 4 【 數(shù)據(jù)規(guī)模 】 對于 50%的數(shù)據(jù)，保證有 n ≤ 20；對于全部的數(shù)據(jù)，保證有 n≤100。 halt。 for i:=1 to n do //階段 i:按照物品數(shù)遞增的順序考慮裝箱情況 begin f1:=f0。顯然 f[i， j]=f[i1， jbox[i]]，即物品 i裝入箱子后的體積正好為 j的前提是 f[i1， jbox[i]]=true。 end。 for i:=1 to 6 do read(a[i])。位于（ x， y）左方且可達(dá)（ x， y）的跳馬位置集合都是（ x， y）的子問題，起點(diǎn)至（ x， y）的路徑數(shù)實(shí)際上等于起點(diǎn)至這些位置集的路徑數(shù)之和（圖 4）。即圖所示： 當(dāng) N， M 給出之后，同時(shí)給出馬起始的位置和終點(diǎn)的位置，試找出從起點(diǎn)到終點(diǎn)的所有路徑的數(shù)目。因此，求所有線中最多能有多少條線不相交，實(shí)際上是從終點(diǎn)坐標(biāo)值數(shù)列中求一個(gè)最長不下降序列。 【 輸出格式 】 輸出文件 ()：要在連續(xù)的若干行里給出每一組數(shù)據(jù)在安全條件下能夠開通的最大航線數(shù)目。每一對友好城市都希望有一條航線來往，于是他們向政府提出了申請。,k)。 //k地窖是 i地窖最優(yōu)路徑 end。 f[n,1]:=w[n]。 fillchar(a,sizeof(a),false)。 begin assign(input,39。很明顯，題目規(guī)定所有路徑都是單向的，所以滿足無后效性原則和最優(yōu)化原理。 end。 for i:= n1 downto 1 do //從終點(diǎn)往前逆推，計(jì)算最短路徑 for x:= i+1 to n do //若 f[x]=maxint表示城市 x到終點(diǎn)城市不通 if (a[i,x]0) and (f[x]maxint) and (f[i]a[i,x]+f[x]) //a[i,x]0表示城市 i和城市 x通路 then begin f[i]:=a[i,x]+f[x]。39。 【 樣例輸入 】 10 0 2 5 1 0 0 0 0 0 0 0 0 0 0 12 14 0 0 0 0 0 0 0 0 6 10 4 0 0 0 0 0 0 0 13 12 11 0 0 0 0 0 0 0 0 0 0 3 9 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 【 樣例輸出 】 minlong=19 1 3 5 8 10 【 算法分析 】 逆推法 設(shè) f(i)表示點(diǎn) i到 v10的最短路徑長度，則 f(10)=0 f(i)=min{ a[i,x]+f(x) 當(dāng) a[i,x]0 ,ix=n} 【 參考程序 】 （逆推法） program short。 //新增一套導(dǎo)彈攔截系統(tǒng) h[x]:=a[i]。 for j:=1 to i1 do //計(jì)算前 i1個(gè)導(dǎo)彈最佳攔截的方案 if a[j]=a[i] then if b[j]max then max:=b[j]。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)。 高效算法是這樣的：用 a[x]表示原序列中第 x個(gè)元素， b[x]表示長度為 x的不下降子序列的最后一個(gè)元素的最小值， b數(shù)組初值為無窮大。 end。 for i := 1 to n do //枚舉求出一套系統(tǒng)能攔截的最多導(dǎo)數(shù) if b[i] max then begin max := b[i]。 k := 0。 begin n := 0。計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。 end。 end。 for i:=n1 downto 1 do //求最長不下降序列 begin