1、動態規劃初步作者:日期:第八講動態規劃初步一、動態規劃簡介,1 957動態規劃是運籌學的一個分支。它是解決多階段決策過程最優化問題的一種方法。 51年，美國數學家貝爾曼(R . B el 1 man提出了解決這類問題的“最優化原則” 年發表了他的名著動態規劃，該書是動態規劃方面的第一本著作。動態規劃問世以來， 在工農業生產、經濟、軍事、工程技術等許多方面都得到了廣泛的應用，取得了顯著的效果。動態規劃運用于信息學競賽是在90年代初期，它以獨特的優點獲得了出題者的青睞。此后，它就成為了信息學競賽中必不可少的一個重要方法，幾乎在所有的國內和國際信息學競賽中，都至少有一道動態規劃的題目。所以，掌握好動

2、態規劃，是非常重要的。動態規劃是一種方法，是考慮問題的一種途徑，而不是一種算法。因此，它不像深度優先 和廣度優先那樣可以提供一套模式。 它必須對具體問題進行具體分析。 需要豐富的想象力和 創造力去建立模型求解。例8- 1 攔截導彈某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一 個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。輸入導彈依次飛來的高度(雷達給出的高度數據是不大于30 0 00的正整數)，計算這套系統最多能攔截多

3、少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。INPUTOU T PUT3 89 2071 5 5 3 0 0 2 9 91701 5 8 656 (最多能攔截的導彈數 )2(要攔截所有導彈最少要配備的系統數)樣例：? ? ?問題分析第一部分是要求輸入數據串中的一個最長不上升序列的長度，可使用遞推的方法，具體做法是從序列的第一個元素開始，依次求出以第i個元素為最后一個元素時的最長不上升序列的長度 len(i),遞推公式為 I en (1)=1 , 1 en(i)=ma x (le n (j )+ 1 )，其中 i > 1 ,j=1,2，i-1 , 且j同時要滿足條件：序列中

4、第J個元素大于等于第1個元素。不上升序列的辦法，然后得出總次數，其實這是不對的。 序列“ 75 4 1 6 32”，最長不上升序列為“果為3套系統；但其實只要 2套，分別擊落“7 又是什么呢？我們的目標是用最少的系統擊落所有導彈，所以很容易受前面的影響，采取多次求最長要舉反例并不難，比如長為7的高度4 3 2”，用多次求最長不上升序列的結4 1 ”與“6 32 ”。那么，正確的做法第二部分比較有意思。由于它緊接著第一問，至于系統之間怎么分配導彈數目則無關緊 要；上面錯誤的想法正是承襲了 “一套系統盡量多攔截導彈”的思維定勢，忽視了最優解中各個系統攔截數較為平均的情況，本質上是一種貪心算法。如果

5、從每套系統攔截的導彈方面來想行不通的話，我們就應該換一個思路，從攔截某個導彈所選的系統入手。題目告訴我們，已有系統目前的瞄準高度必須不低于來犯導彈高度，所以，當已有的系 統均無法攔截該導彈時，就不得不啟用新系統。如果已有系統中有一個能攔截該導彈，我們是應該繼續使用它，還是另起爐灶呢？事實是：無論用哪套系統，只要攔截了這枚導彈，那么系統的瞄準高度就等于導彈高度，這一點對舊的或新的系統都適用。而新系統能攔截的導彈高度最高，即新系統的性能優于任意一套已使用的系統。既然如此，我們當然應該選擇已 有的系統。如果已有系統中有多個可以攔截該導彈，究竟選哪一個呢？當前瞄準高度較高的系統的“潛力”較大，而瞄準高

6、度較低的系統則不同，它能打下的導彈別的系統也能打下，它,要選瞄準高度夠不到的導彈卻未必是別的系統所夠不到的。所以，當有多個系統供選擇時 最低的使用，當然瞄準高度同時也要大于等于來犯導彈高度。解題時，用一個數組記下已有系統的當前瞄準高度，數據個數就是系統數目。 程序清單gi nt;c o nst max = 1 0 00;va r i ,j,c urr en t, maxlong,m i nheight, se lect,t a i 1, total:lon height,1 on gest, sys:ar ray 1. ma x o f Ion gi nt;1i ne:string;begin

7、w r ite (' I npu t test data:');readln( 1 ine);i: =1;w h i le i< = len gth (line) d o(i <=l e ngth(1i ne ) and (linei=' /) urr e n t:=0;do i:=i + 1;beg i nw hil el e (i< = 1 eng th (1 i n e)and (lin e i< >'')dow hib egi ncurren t : = cur r ent*10+ o rd (1 in e i)-o

8、rd('0 Q ;i: =i + 1en d;tot a l := t o ta 1 +1;h eightt o t a l:=cu r renten d;1 o n gest1:=1;for i:=2 to t o tal d obeginm ax 1o n g := 1;f or j: = 1 to i - 1 dob e g inif h e ig h t i< = h ei gh t j t h e n if 1 ong e st j + 1>max 1 on gth en max Iong:=lo n ge s t j +1 ;Ion ge st i :=maxl

9、 on gen d;en d;maxlo n g:=lo n ge s t1;f o r i:=2 t o to ta l d oi f 1 ong e s t i > max 1o ng t h en maxi o n g:=lo n g est i ; wr i teln (m a xlon g );:=he i ght 1; tai 1 : = 1; to total dosys1:for i:=2beg iminheight:=maxi n t;f 0 r j ：=1 to tai l doi f sysj >heigh t i the nif sysj< min h

10、eigh t th enbeg i n minhe i ght:= s ys j ; select:=j end ;i f mi nhe i gh t=max in tt hen be gin t a il: = tail+1; sys t ai 1 :=heigh ti end else sy s se 1 ect:=heighti e nd ;writ e l n ( t ail)e nd.二、動態規劃的幾個基本概念想要掌握好動態規劃，首先要明白幾個概念：階段、狀態、決策、策略、指標函數。階段：把所給問題的過程，恰當地分為若干個相互聯系的階段，以便能按一定的次序去求解。描述階段的變量稱為階

11、段變量。狀態：狀態表示每個階段開始所處的自然狀況和客觀條件，況,又稱不可控因素。決策：決策表示當過程處于某一階段的某個狀態時， 可以作出不同的決定(或選擇),從而 確定下一階段的狀態，這種決定稱為決策 ，在最優控制中也稱為控制。描述決策的變量 ， 稱為決策變量。策略：由所有階段的決策組成的決策函數序列稱為全過程策略，簡稱策略。狀態轉移方程：狀態轉移方程是確定過程由一個狀態到另一個狀態的演變過程。指標函數：用來衡量所實現過程優劣的一種數量指標，稱為指標函數。指標函數的最優值，稱為最優值函數。三、確定動態規劃的思路1、采用動態規劃來解決問題，必須符合兩個重要的條件。(1) “過去的歷史只能通過當前

12、狀態去影響它未來的發展，當前的狀態是對以往歷史的一個 總結”，這種特性稱為無后效性，是多階段決策最優化問題的特征。(2 )作為整個過程的最優策略具有這樣的性質：即無論過去的狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。簡言之，一個最優策略的子策略總是最優的。這就是最優化原理。2、如果碰到一個問題，能夠滿足以上兩個條件的話 ，那么就可以去進一步考慮如何去設計使 用動態規劃：(1)劃分階段。把一個問題劃分成為許多階段來思考(2) 設計合適的狀態變量(用以遞推的角度)(3 )建立狀態轉移方程(遞推公式)(4)尋找邊界條件(已知的起始條件) 如果以上幾個步驟都成功完成的話

13、，我們就可以進行編程了。四、動態規劃解題的一些技巧仙于動態規劃并沒有一個定式，這就需要去開拓我們創造力去構造并且使用它。以下 一些具體的競賽實例談談使用動態規劃過程中的一些技巧。例8 2堆塔問題，設有n個邊長為1的正立方體，在一個寬為 1的軌道上堆塔，但塔本 身不能分離。例如n =1時，只有1種方案1.2.3.4.5.6.它描述了研究問題過程中的狀,通過種方案堆塔的規則為底層必須有支撐，如下列的堆法是合法的 總共有多少種不同的方案 堆成每層的方案數是多少，例如n=6時，堆成1層的方案數為1,堆成6層的方案數為1 問題分析問題的分析見第七講例7-3,列去掉的話，則成為一個比n小的堆塔問題， 法是

14、從1到n依次求出堆成每層的方案數，設關于問題，可以這樣考慮，將n個立方體的第一 這樣問題就可以用動態規劃法來解。具體方f(n,k)為堆成k層的方案數,則遞推公式為：k 1kf( n,k) f(n i,k) f(n k,i)i 1i 1算法設計由于n最大可達到4 0,所以堆塔的總方案數超過了長整形數的范圍，程序 采用了高精度加法運算。程序清單Progr am ex8 2( in pu t, o ut p ut);const maxn=40; ma xl en = m ax n div 3;ty p e a rra yt yp e =arr a y0.maxle n of int e ger;va

15、 r i , j , k, n, n n :longint;tot a l:a r raytypf:arraproced uva r i :b egi nfolongie ;y 0. ma xn,O.maxn a dd(v ar a:arr a ytype ;of arr a ytype; b:arraytyp e);nt ；:=0 to ma X len d o ai:=ai+b : i;fo r i : =0tom a X len-1 d oifa i :> =10 t h enbegi nai+1： :=ai+1：ai:=ai -10e n dend ;proc e dur e p

16、r int(a:arraytyp e);gin t ;n+ 1r iva r i , j : lo begini:=maxle n;whil e f o r j: end;be g in(i > 0)and=i do w nto 0(a :i=0)d o wri t e(a j )d o i: = i-1;write(/Inpu tn:');read1n(n);fori 1 t omaxle ndo tot a1 ：i :total0 :=1;fori:=1t o n-1doa d d(tot al,to tal );fori:=1to maX ndof or .j:=1t om

17、a Xn dofork :=0 to m a xl en dof： i, Jf or i:=1to max nd ofi,1,0:=1 ；for i:=1t oma xn dofi,i,0:=1;f ornn:=2 ton dIok : = 0 ；-1 dof or k:=2 to n n=0begifor i:=1 to f or i : =1 to kk-1 do addod (fn n, k,fnn-l, k);n n-k>=i th en add(fnn ,kf nn-k , i:)en d;wri t e('Tot nt( total);a l =')；priw

18、ritel n;for k : =1 t o n do b e ginw r l te( / print(fn, w rite 1 n;k modifHe ik：g ht = ',k:2 ,'K l n d =' : 1 0 );)；23 = 0h enbegiw rit e (/p ress < E nter> to continue! readln/ )；en de nd;wriPr es S <Enter> t o contin u e!');en d.例 8-3readl n:投資問題：有n萬元的資金，可投資于m個項目，其中m 和

19、n為小于1 0 0的自然數。對第i (1 <i Wm)個項目投資j萬元(1 Wj Wn,且j為整數)可獲得的回報為 Q (i , j),請編程序，求 解并輸出最佳的投資方案(即獲得回報總值最高的投資方案輸入數據放在一個文本文件中，格式如下：m nQ(1,0) Q (1 , 1)Q (1, n)Q(2,0 )Q(2, 1)Q (2, n)Q(m , 0) Q(m ,1)Q(m , n)輸出數據格式為：r(1)r(2) r (m) P其中r(i) (1WiW m)表示對第i個項目的投資萬元數，P為總的投資回報值，保留兩位有效數字，任意兩個數之間空一格。當存在多個并列的最佳投資方案時，只要求輸

20、出其中之一即可。如輸入數據如下時：200屏幕應輸出：131 . 11.31 .92.12. 52.623 .6問題分析本題可供考慮的遞推角度只有資金和項目兩個角度，從項目的角度出發，逐個項目地增加可以看出只要算出了對前k個項目投資j萬元最大投資回報值(1 < j< n),就能推出增加第k+1個項目后對前k+1個項目投資j萬元最大投資回報值(1 <j< n),設Pk,j為前k 個項目投資j萬元最大投資回報值，則Pk + 1 ,j = Max (Pk,1 +Q k +1,j i),0<=i < =j,k= 1時，對第一個項目投資J萬元最大投資回報值(0<j

21、< n)是已知的(邊界條件)。算法設計動態規劃的時間復雜度相對于搜索算法是大大降低了，卻使空間消耗增加了很 多。所以在設計動態規劃的時候，需要盡可能節省空間的占用。原始數據和最大投資回報值的話，將造成空間不夠，事實上 算對前k+1個項目投資J萬元最大投資回報值時，只要用到矩陣 k個項目投資J萬元最大投資回報值，而與前面的數據無關，儲即可，程序中用一維數組 Q存儲當前項目的投資回報值，用一維數組m axr etu r n存儲對當前項目之前的所有項目投資j萬元最大投資回報值(owjwn),用一維數組tem p存儲對到當前項目為止的所有項目投資J萬元最大投資回報值(0< j< n)

22、。為了輸出投資方案，程序中使用了一個二維數組in V es t, in ve s tk,j :記錄了對前k個項目投資j萬元獲得最大投資回報時投資在第k個項目上的資金數。程序清單pro g r am ex8_3(input,outpu t ); con st m axm=100; max n=1 O 0;type arra y t yp e=ar r ay O. .maxn of re a l ;V a r i ，j, k，m , n , r est:i n t e ger;q , maxr e tu r n，temp：ar ray t y p e;i nv e s t:a rra y u lt

23、: a rray1.m nam e:s t ring;text ;本題中如果用二維數組存儲,從前面的問題分析可知：在計Q的第k+1行數據和對前 后者也只需有一個一維數組存 ，用一維數組m ares1 .maxm,0 .ax m of.ma x n of i nt e ger; i nte g e r;ff:begi nwrite('I n pu t the n ame of data file :');r e ad In (f n ame);a s sig n (f,fname););(f , m, n);=0 t on d o readn (f)；=1 to m dore S

24、 et(f re a dln for j:re a d lfo r i:(f,qj)；fo r j:=0 to maxret u rn: = q; f or j : =0 to n fo r k : = 2 to b eg i n tempforn d o i nv esdo inv e s t 1, m dof ore ad=maxr e tu rn;j:= 0J :=0 tl n(f)；to n do inv o n doti ,J ： = 0；j ：= J ；est :k, j:=0;re a d ( f , q j);f or j:=0 tofon doi:=0 t oifmax re

25、J dot urnj-i+qi > tempjthen=mak,j:xr etur n j-i+q i;=ib eg intemp j: i n vesmaen d; rn : =te mpen d;c loseresforbeg(f);t : = n;i:= m dow nto 1indo,rest resu It i : =in ve st r es t: = r e s t res u l t e n d;forwritei:=1 to m d o write (resu l ti,'1 n(max r eturnn:0:2)')；例 8-4 花店櫥窗布置問題(F

26、L OWE R)(1 )問題描述假設你想以最美觀的方式布置花店的櫥窗。現在你有en d.F束不同品種的花束，同時你也 有至少同樣數量的花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從1至V順序編號,V是花瓶的數目，從左至右排列 ，則最左邊的是花瓶 1,最右邊的是花瓶 V。花束可以移 動,并且每束花用1至F間的整數唯一標識。標識花束的整數決定了花束在花瓶中的順序，如果IV J,則令花束I必須放在花束J左邊的花瓶中。例如，假設一束杜鵑花的標識數為 1 , 一束秋海棠的標識數為 2, 一束康乃馨的標識數 為3,所有的花束在放入花瓶時必須保持其標識數的順序，即：杜鵑花必須放在秋海棠左邊 的花瓶中

27、，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數目大于花束的數目。則多余的花瓶必須空置，且每個花瓶中只能放一束花。每一個花瓶都具有各自的特點。因此，當各個花瓶中放入不同的花束時 ，會產生不同的美學效果，并以美學值(一個整數)來表示，空置花瓶的美學值為零。 在上述例子中，花瓶與花束的不同搭配所具有的美學值，如下表所示。花瓶12345花束1（杜鵑花）7235-241 62（秋海棠）521-4102 33（康乃馨）-215-4-2020例如，根據上表，杜鵑花放在花瓶2中，會顯得非常好看；但若放在花瓶4中則顯得十分難看。為取得最佳美學效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學 值。

28、如果有不止一種的擺放方式具有最大的美學值，則其中任何一直擺放方式都可以接受但你只要輸出任意一種擺放方式。?（ 2）假設條件F。K FW1 00,其中F為花束的數量，花束編號從1至 F<V< 100 ,其中V是花瓶的數量。-5 0< AijW 50,其中A是花束i在花瓶j中的美學值。輸入輸入文件是正文文件 （t ex t f ile），文件名是fl o wer .i n p。第一行包含兩個數：F, V。隨后的F行中，每行包含V個整數，Aj即為輸入文件中第（i +1 ）行中的第j個數。輸出輸出文件必須是名為 fl ow e r . ou t的正文文件，文件應包含兩行 第一行是程序

29、所產生擺放方式的美學值。K個數表示花束K所在的花瓶的編號。第二行必須用F個數表示擺放方式，即該行的第(5 )例子f Io w er.inp:3 57 23-5 -24 165 21 -4 10 23-21 5 -4 -20 20f l o wer .0 u t :532 4 5?6 )評分程序必須在2秒中內運行完畢。在每個測試點中，完全正確者才能得分。算法設計flower 一題是I 01 9 9第一天第一題，該題如用組合的方法處理，將會造成超時。 正確的方法是用動態規劃，考慮角度為一束一束地增加花束，假設用b(i,j)表示1i束花放在1到j之間的花瓶中的最大美學值，其中i<=j，則b (

30、i ,j)= max(b i 1,k-1+ A i ,k:),其中i <= k< =j j A (i ,k )的含義參見題目。輸出結果時，顯然使得bF, k取得總的最大美觀值的第一個 k值就是第F束花應該擺放的花瓶位置，將總的最大美觀值減去Ai j k 的值即得到前k-1束花放在前k-1個瓶中的最大美觀值，依次使用同樣的方法就可求出每一束花 應該擺放的花瓶號。由于這一過程是倒推出來的，所以程序中用遞歸程序來實現。程序清單P r og ra m ex8_4(i nput ,outpu t);const m a x= 100;var f ,v,i,j,k , c max, cur r ent,maxv a1 :in t eg er ;tab le,val:arr ay 1. max ,1.ma x of in t eger;f n ame:string;fin:text;pro ce dure print(current , max_ v a 1 :in te g e r);va r i：i nteger;b eg i ncu r r e nt >0 t h enbegini := c urren t ;w h ile v al c u rre nt, i < >