第9章第1-2節(jié)動態(tài)規(guī)劃基礎(chǔ)(C++版)

1、第九章第九章 動態(tài)規(guī)劃動態(tài)規(guī)劃第一節(jié)第一節(jié) 動態(tài)規(guī)劃的基本模型動態(tài)規(guī)劃的基本模型第二節(jié)第二節(jié) 動態(tài)規(guī)劃與遞推動態(tài)規(guī)劃與遞推第三節(jié)第三節(jié) 背包問題背包問題第四節(jié)第四節(jié) 動態(tài)題動態(tài)題 動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必

2、須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。第一節(jié)第一節(jié) 動態(tài)規(guī)劃的基本模型動態(tài)規(guī)劃的基本模型w多階段決策過程的最優(yōu)化問題多階段決策過程的最優(yōu)化問題 在現(xiàn)實(shí)生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一

3、個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。如下圖所示： 多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列?！纠纠?】最短路徑問題。最短路徑問題。下圖給出了一個地圖，地圖中的每個頂點(diǎn)代表一個城市，兩個城市間的一條連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在想從城市A到達(dá)城市E，怎樣走路程最短？最短路程的長度是多少？【算法分析】【算法分析】 把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第

4、2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路。用DK（XI，X+1J）表示在第K階段由初始狀態(tài)XI到下階段的初始狀態(tài)X+1J的路徑距離，F(xiàn)K（XI）表示從第K階段的XI到終點(diǎn)E的最短距離，利用倒推的方法，求解A到E的最短距離。 具體計算過程如下：S1： K = 4 有 F4（D1）= 3， F4（D2）= 4， F4（D3）= 3；S2： K = 3 有 F3（C1）= MIN D3（C1，D1）+ F4（D1），D3（C1，D2）+ F4（D2） = MIN 5+3，6+4 = 8 F3（C2）= D3（C2，D1）+ F4（D1）= 5+3 = 8 F

5、3（C3）= D3（C3，D3）+ F4（D3）= 8+3 = 11 F3（C4）= D3（C4，D3）+ F4（D3）= 3+3 = 6S3： K = 2 有 F2（B1）= MIN D2（B1，C1）+ F3（C1），D2（B1，C2）+ F3（C2）， D2（B1，C3）+ F3(C3) = MIN 1+8,6+8,3+11 = 9 F2（B2）= MIN D2（B2，C2）+ F3（C2），D2（B2，C4）+ F3（C4） = MIN 8+8，4+6 = 10S4： K = 1 有 F1（A）= MIN D1（A，B1）+ F2（B1），D1（A，B2）+ F2（B2） = MIN

6、5+9，3+10 = 13 因此由A點(diǎn)到E點(diǎn)的全過程最短路徑為AB2C4D3E；最短路程長度為13。 從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到終點(diǎn)E的最短距離，當(dāng)逆序倒推到過程起點(diǎn)A時，便得到了全過程的最短路徑和最短距離。 在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設(shè)計方法。w動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成 現(xiàn)在我們來介紹動態(tài)規(guī)劃的基本概念。1. 階段和階段變量

7、： 用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示，階段的劃分一般是根據(jù)時間和空間的自然特征來劃分，同時階段的劃分要便于把問題轉(zhuǎn)化成多階段決策過程，如例題1中，可將其劃分成4個階段，即K = 1，2，3，4。2. 狀態(tài)和狀態(tài)變量： 某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。如例題1中，C3是一個狀態(tài)變量。3. 決策、決策變量和決策允許集合： 在對問題的處理中作出的每種選擇性的行動就是決策。即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性

8、的行動轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。一個實(shí)際問題可能要有多次決策和多個決策點(diǎn)，在每一個階段的每一個狀態(tài)中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實(shí)際問題中，決策變量的取值往往限制在某一個范圍之內(nèi)，此范圍稱為允許決策集合。如例題1中，F(xiàn)3（C3）就是一個決策變量。4策略和最優(yōu)策略： 所有階段依次排列構(gòu)成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實(shí)際問題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策略。5. 狀態(tài)轉(zhuǎn)移方程 前一階段的終點(diǎn)就是后一階段的起點(diǎn)，對前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律

9、，稱為狀態(tài)轉(zhuǎn)移方程。w最優(yōu)化原理與無后效性最優(yōu)化原理與無后效性 上面已經(jīng)介紹了動態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。 一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)化原理和無后效性原則： 1、動態(tài)規(guī)劃的最優(yōu)化原理。作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解為子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，而非最優(yōu)解對問題的求解沒有影響。在例題1最短路徑問題中，

10、A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑，也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個局部優(yōu)化。 2、動態(tài)規(guī)劃的無后效性原則。所謂無后效性原則，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個完整的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。在例題1最短路徑問題中，問題被劃分成各個階段之后，階段K中的狀態(tài)只能由階段K+1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其它狀態(tài)沒有關(guān)系，特別與未發(fā)生的狀態(tài)沒有關(guān)系，例如從Ci到E的最短路徑，只與Ci的位置有關(guān)，它是由Di中的狀態(tài)通過狀態(tài)轉(zhuǎn)

11、移方程得來，與E狀態(tài)，特別是A到Ci的路徑選擇無關(guān)，這就是無后效性。 由此可見，對于不能劃分階段的問題，不能運(yùn)用動態(tài)規(guī)劃來解；對于能劃分階段，但不符合最優(yōu)化原理的，也不能用動態(tài)規(guī)劃來解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無后效性原則，還是不能用動態(tài)規(guī)劃來解；誤用動態(tài)規(guī)劃程序設(shè)計方法求解會導(dǎo)致錯誤的結(jié)果。w動態(tài)規(guī)劃設(shè)計方法的一般模式動態(tài)規(guī)劃設(shè)計方法的一般模式 動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)；或倒過來，從結(jié)束狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到初始狀態(tài)。這些決策形成一個決策序列，同時確定了完成整個過程的一條活動路線，

12、通常是求最優(yōu)活動路線。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟：1、劃分階段 按照問題的時間或空間特征，把問題劃分為若干個階段。在劃分階段時，注意劃分后的階段一定是有序的或者是可排序的，否則問題就無法求解。2、確定狀態(tài)和狀態(tài)變量 將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。3、確定決策并寫出狀態(tài)轉(zhuǎn)移方程 因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩段的各個狀態(tài)之間的關(guān)系來確定決策。4、尋找邊界條件 給出的

13、狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件?！纠?】對應(yīng)的C+程序如下：#include#includeusing namespace std;int main() long d555,f1010; memset(d,42,sizeof(d); /有些路徑是不通的,賦值為較大值，用于判斷 d111=5;d112=3;d211=1; /以下給可通路徑賦正常值 d212=6;d213=3;d222=8 d224=4;d311=5;d312=6; d321=5;d333=8;d343=3; d411=3;d421=4;d431=3; for (int i=0;i=9;+i) for

14、(int j=0;j=1;-i) for (int j=1;j=4;+j) for (int k=1;kdijk+fi+1k) /即使走非法路徑，也不影響答案 fij=dijk+fi+1k; coutf11endl;第二節(jié)第二節(jié) 動態(tài)規(guī)劃與遞推動態(tài)規(guī)劃與遞推 動態(tài)規(guī)劃是最優(yōu)化算法動態(tài)規(guī)劃是最優(yōu)化算法 由于動態(tài)規(guī)劃的“名氣”如此之大，以至于很多人甚至一些資料書上都往往把一種與動態(tài)規(guī)劃十分相似的算法，當(dāng)作是動態(tài)規(guī)劃。這種算法就是遞推。實(shí)際上，這兩種算法還是很容易區(qū)分的。 按解題的目標(biāo)來分，信息學(xué)試題主要分四類：判定性問題、構(gòu)造性問題、計數(shù)問題和最優(yōu)化問題。我們在競賽中碰到的大多是最優(yōu)化問題，而動態(tài)

15、規(guī)劃正是解決最優(yōu)化問題的有力武器，因此動態(tài)規(guī)劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數(shù)問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態(tài)規(guī)劃在這兩個方面的聯(lián)系?！纠?】數(shù)塔問題（數(shù)塔問題（IOI1994）有形如圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。 這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如40），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目。如果用貪心法又往往得不到最優(yōu)解。在用動態(tài)規(guī)劃考慮數(shù)塔問題時可以自頂向下的分析，自底向上的計算。從頂點(diǎn)出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最

16、大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。所以實(shí)際求解時，可從底層開始，層層遞進(jìn)，最后得到最大值。 一般說來，很多最優(yōu)化問題都有著對應(yīng)的計數(shù)問題；反過來，很多計數(shù)問題也有著對應(yīng)的最優(yōu)化問題。因此，我們在遇到這兩類問題時，不妨多聯(lián)系、多發(fā)展，舉一反三，從比較中更深入地理解動態(tài)規(guī)劃的思想。 其實(shí)遞推和動態(tài)規(guī)劃這兩種方法的思想本來就很相似，也不必說是誰借用了誰的思想。關(guān)鍵在于我們要掌握這種思想，這樣我們無論在用動態(tài)規(guī)劃法解最優(yōu)化問題，或是在用遞推法

17、解判定型、計數(shù)問題時，都能得心應(yīng)手、游刃有余了。【解法一】（逆推法）【解法一】（逆推法）【算法分析】【算法分析】 貪心法往往得不到最優(yōu)解：本題若采用貪心法則：13-11-12-14-13，其和為63,但存在另一條路：13-8-26-15-24，其和為86。 貪心法問題所在：眼光短淺。 動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為：自頂向下的分析，自底向上計算。 其基本方法是： 劃分階段：按三角形的行，劃分階段，若有n行，則有n-1個階段。 A從根結(jié)點(diǎn)13出發(fā)，選取它的兩個方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時，每個結(jié)點(diǎn)其后繼僅有兩個結(jié)點(diǎn)，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點(diǎn)開始到底端

18、的最大路徑。 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 最后的路徑：138261524 C數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計 圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右 用三維數(shù)組表示數(shù)塔：axy1表示行、列及結(jié)點(diǎn)本身數(shù)據(jù),axy2能夠取得最大值,axy3表示前進(jìn)的方向0向下，1向右； 算法： 數(shù)組初始化，

19、輸入每個結(jié)點(diǎn)值及初始的最大路徑、前進(jìn)方向?yàn)?； 從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán)N-1次； 從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的值比原先多1則向右，否則向下。 參考程序參考程序#include#includeusing namespace std;int main()int n,x,y;int a51513;coutn;memset(a,0,sizeof(0);for (x=1;x=n;x+) /輸入數(shù)塔的初始值輸入數(shù)塔的初始值 for (y=1;yaxy1;axy2=axy1;axy3=0; /路徑走向，默認(rèn)向下路徑走向，默認(rèn)向下 for (x=n-1;x=1;

20、x-) for (y=1;yax+1y+12) /選擇路徑，保留最大路徑值選擇路徑，保留最大路徑值 axy2=axy2+ax+1y2; axy3=0; else axy2=axy2+ax+1y+12; axy3=1; coutmax=a112endl; /輸出數(shù)塔最大值輸出數(shù)塔最大值 y=1; for (x=1;x=n-1;x+) /輸出數(shù)塔最大值的路徑輸出數(shù)塔最大值的路徑 coutaxy1; y=y+axy3; /下一行的列數(shù)下一行的列數(shù) coutany18-26-15-24【解法二】（順推法）【解法二】（順推法）【算法分析】【算法分析】 此題貪心法往往得不到最優(yōu)解，例如13-11-12-1

21、4-13其路徑的值為63，但這不是最優(yōu)解。 窮舉搜索往往是不可能的，當(dāng)層數(shù)N = 100時，路徑條數(shù)P = 299這是一個非常大的數(shù)，即使用世界上最快的電子計算機(jī)，也不能在規(guī)定時間內(nèi)計算出來。 對這道題唯一正確的方法是動態(tài)規(guī)劃。如果得到一條由頂?shù)降椎哪程幍囊粭l最佳路徑，那么對于該路徑上的每一個中間點(diǎn)來說，由頂點(diǎn)至該中間點(diǎn)的路徑所經(jīng)過的數(shù)字和也為最大。因此本題是一個典型的多階段決策最優(yōu)化問題。在本題中僅要求輸出最優(yōu)解，為此我們設(shè)置了數(shù)組Ai,j保存三角形數(shù)塔，Bi,j保存狀態(tài)值，按從上往下方式進(jìn)行求解。 階段i：以層數(shù)來劃分階段，由從上往下方式計算；因此可通過第一重循環(huán): for (int i=

22、1;i=n;i+) 枚舉每一階段； 狀態(tài)Bij：由于每個階段中有多個狀態(tài)，因此可通過第二重循環(huán): for (int j=1;j=i;j+)求出每個階段的每個狀態(tài)的最優(yōu)解Bij； 決 策：每個狀態(tài)最多由上一層的兩個結(jié)點(diǎn)連接過來，因此不需要做循環(huán)。 【參考程序】【參考程序】#include#includeusing namespace std;int main()int n,i,j,a200200,b200200,maxx; cinn; memset(a,0,sizeof(a); memset(b,0,sizeof(b); for (i=1;i=n;+i)for (j=1;jaij; bij=ai

23、j; for (i=2;i=n;+i) /選擇路徑，保留最大路徑值 for (j=1;jbi-1j) bij=bij+bi-1j-1; else bij=bij+bi-1j; maxx=0; for (j=1;jmaxx) /在第n行中找出數(shù)塔最大值 maxx=bnj; coutMax=maxxendl; /輸出數(shù)塔最大值 【例【例3】求最長不下降序列】求最長不下降序列問題描述： 設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:b(1)、b(2)、b(n)且b(i)b(j) (ij)，若存在i1i2i3 ie 且有b(i1)b(i2) b(ie)則稱為長度為e的不下降序列。程序要求，當(dāng)原數(shù)列出之后，求

24、出最長的不下降序列。 例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一個長度為7的不下降序列，同時也有7 ，9，16，18，19，21，22，63長度為8的不下降序列。算法分析： 根據(jù)動態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索(當(dāng)然從前往后也一樣)。 1對b(n)來說，由于它是最后一個數(shù)，所以當(dāng)從b(n)開始查找時，只存在長度為1的不下降序列； 2若從b(n-1)開始查找，則存在下面的兩種可能性： 若b(n-1)b(n)則存在長度為1的不下降序列b(n-1)或b(n)。 3一般若從b(i)開始，此時最長不下降序列應(yīng)該按

25、下列方法求出:在b(i+1),b(i+2),b(n)中，找出一個比b(i)大的且最長的不下降序列，作為它的后繼。數(shù)據(jù)結(jié)構(gòu)： 為算法上的需要，定義一個整數(shù)類型二維數(shù)組b(N,3) 1b(I,1)表示第I個數(shù)的數(shù)值本身； 2b(I,2)表示從I位置到達(dá)N的最長不下降序列長度 3b(I,3)表示從I位置開始最長不下降序列的下一個位置，若bI,3=0則表示后面沒有連接項(xiàng)。 求解過程： 從倒數(shù)第二項(xiàng)開始計算，后面僅有1項(xiàng)，比較一次，因6315，不符合要求，長度仍為1。 從倒數(shù)第三項(xiàng)開始其后有2項(xiàng)，需做兩次比較，得到目前最長的不下降序列為2，如下表：1112131411121314226315212263

26、1521132111300121300 一般處理過程是： 在i+1,i+2,n項(xiàng)中，找出比bI,1大的最長長度L以及位置K; 若L0，則bI,2:=L+1;bI,3:=k; 最后本題經(jīng)過計算，其數(shù)據(jù)存儲表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for (i=1;ibi1; bi2=1;bi3=0;下面給出求最長不下降序列的算法:for (i=n-1;i=1;i-) l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if (l0

27、) bi2=l+1; bi3=k; 下面找出最長不下降序列：k=1;for (j=1;jbk2) k=j;最長不下降序列長度為bk2序列while (k!=0) coutbk1; k=bk3;#includeusing namespace std;int main() int n,i,j,l,k,b20010; coutinput n:n; for (i=1;ibi1; bi2=1;bi3=0; 程序運(yùn)行結(jié)果：輸入：1413 7 9 16 38 24 37 18 44 19 21 22 63 15輸出：max=87 9 16 18 19 21 22 63 for (i=n-1;i=1;i-)

28、/求最長不下降序列 l=0;k=0; for (j=i+1;jbi1)&(bj2l) l=bj2; k=j; if (l0) bi2=l+1;bi3=k; k=1; for (j=1;jbk2) k=j; coutmax=bk2endl; /輸出結(jié)果 while (k!=0) /輸出最長不下降序列 cout bk1; k=bk3; 【例例4】攔截導(dǎo)彈攔截導(dǎo)彈(Noip1999)某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每攔截系統(tǒng)有一個缺陷：雖然

29、它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，的正整數(shù)，導(dǎo)彈數(shù)不超過導(dǎo)彈數(shù)不超過1000），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套

30、這種導(dǎo)彈攔截系統(tǒng)。彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例：樣例：INPUT OUTPUT389 207 155 300 299 170 158 65 6（最多能攔截的導(dǎo)彈數(shù)）（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）【算法分析算法分析】 第一問即經(jīng)典的最長不下降子序列問題，可以用一般的第一問即經(jīng)典的最長不下降子序列問題，可以用一般的DP算法，也可以用高算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模不需要。效算法，但這個題的數(shù)據(jù)規(guī)模不需要。用用ax表示原序列中第表示原序列中第x個元素，個元素，bx表示長度為表示長度為x的不下降子序列的長的不下

31、降子序列的長度，。當(dāng)處理第度，。當(dāng)處理第ax時，可查找它可以連接到長度最大為多少的不下降子序列時，可查找它可以連接到長度最大為多少的不下降子序列后（即與部分后（即與部分bx比較）。假設(shè)可以連到長度最大為比較）。假設(shè)可以連到長度最大為maxx的不下降子序列后，的不下降子序列后，則則bx:=maxx+1。b數(shù)組被賦值的最大值就是第一問的答案。數(shù)組被賦值的最大值就是第一問的答案。第二問用貪心法即可。每顆導(dǎo)彈來襲時，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)第二問用貪心法即可。每顆導(dǎo)彈來襲時，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來攔截。若不存在符合這一條件的系統(tǒng)，中上一次攔截導(dǎo)彈高度最低的那

32、一套來攔截。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)。則使用一套新系統(tǒng)?！緟⒖汲绦騾⒖汲绦颉浚樛品ǎ樛品ǎ?include#include#includeusing namespace std;int main() freopen(in.txt, r, stdin); freopen(out.txt, w, stdout); int i,j,k,x,n,maxx,m,a10000,b10000,h10000; i=1;n=0;m=0; memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset(h,0,sizeof(h); while (ci

33、nai) maxx=0; for (j=1;j=ai) if (bjmaxx) maxx=bj; bi=maxx+1; if (bim) m=bi; x=0; for (k=1;k=ai) if (x=0) x=k; else if (hkhx) x=k; /如果有多套系統(tǒng)可攔截，則選擇上一次攔截高度最低的 if (x=0) n+;x=n; /新增一套導(dǎo)彈攔截系統(tǒng) hx=ai; i+; coutmendlnE。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A-E的最省費(fèi)用。交通圖1 交通圖2 如圖：求v1到v10的最短路徑長度及最短路徑。【樣例輸入】short.in100 2 5 1 0 0 0 0 0 00

34、0 0 0 12 14 0 0 0 00 0 0 0 6 10 4 0 0 00 0 0 0 13 12 11 0 0 00 0 0 0 0 0 0 3 9 00 0 0 0 0 0 0 6 5 00 0 0 0 0 0 0 0 10 00 0 0 0 0 0 0 0 0 50 0 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0【樣例輸出】short.outminlong=191 3 5 8 10【算法分析】逆推法 設(shè)fi表示點(diǎn)i到v10的最短路徑長度，則 f10=0 fi=min aix+fx 當(dāng)aix0 ,ix=n時#includeusing namespace st

35、d;#include#includeint main() long n,i,j,x,f100,c100,a100100; memset(a,0,sizeof(a); memset(c,0,sizeof(c); cinn; for (i=1;i=n;i+) /輸入各個城市之間距離輸入各個城市之間距離 for (j=1;jaij; for (i=1;i=1;i-) /從終點(diǎn)往前逆推，計算最短路徑從終點(diǎn)往前逆推，計算最短路徑 for (x=i+1;x0)&(fx!=1000000)&(fiaix+fx) /aix0表示城市表示城市i和城市和城市x通路通路 fi=aix+fx; /城市城市i到終點(diǎn)最短

36、路徑的值到終點(diǎn)最短路徑的值 ci=x; coutminlong=f1endl; /輸出最短路徑的值輸出最短路徑的值 x=1;wwhile (x!=0) /輸出路過的各個城市輸出路過的各個城市w w coutx ;w x=cx;w w coutendl; ww【例6】挖地雷w【問題描述】w在一個地圖上有N個地窖（N=200）,每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的,也不存在可以從一個地窖出發(fā)經(jīng)過若干地窖后又回到原來地窖的路徑。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使他能挖

37、到最多的地雷。w【輸入格式】w N /地窖的個數(shù)w W1，W2，WN /每個地窖中的地雷數(shù)w X1，Y1 /表示從X1可到Y(jié)1w X2，Y2w w 0，0 /表示輸入結(jié)束w【輸出格式】w K1-K2-Kv /挖地雷的順序w MAX /最多挖出的地雷數(shù)w【輸入樣例】Mine.inw 6w 5 10 20 5 4 5w 1 2w 1 4w 2 4w 3 4w 4 5w w 4 6w 5 6w 0 0w【輸出樣例】Mine.outw 3-4-5-6w 34w【算法分析】w本題是一個經(jīng)典的動態(tài)規(guī)劃問題。很明顯，題目規(guī)定所有路徑都是單向的，所以滿足無后效性原則和最優(yōu)化原理。設(shè)Wi為第i個地窖所藏有的地雷

38、數(shù)，Aij表示第i個地窖與第j個地窖之間是否有通路，F(xiàn)i為從第i個地窖開始最多可以挖出的地雷數(shù)，則有如下遞歸式：wFi=max Wi+ Fj (ij=n , Aij=true)w邊界：Fn=Wnw于是就可以通過遞推的方法，從后F(n)往前逐個找出所有的Fi，再從中找一個最大的即為問題2的解。對于具體所走的路徑（問題1），可以通過一個向后的鏈接來實(shí)現(xiàn)。w【參考程序】w#includew#includewusing namespace std;wint main()ww long f201=0,w201,c201=0;w bool a201201=0;w long i,j,n,x,y,l,k,ma

39、xx;w memset(f,0,sizeof(f);w wmemset(c,0,sizeof(c);w memset(a,false,sizeof(a);w cinn;w for (i=1;iwi; /輸入每個地窖中的地雷數(shù)w dow w cinxy; /表示從X可到Y(jié)w if (x!=0)&(y!=0) axy=true;w while (x!=0)|(y!=0);w fn=wn; /從后Fn往前逐個找出所有的Fiw for (i=n-1;i=1;i-)w w l=0;k=0;w for (j=i+1;jl)w l=fj; k=j; w fi=l+wi; /保存從第i個地窖起能挖到最大地雷數(shù)

40、w ci=k; /k地窖是i地窖最優(yōu)路徑w w k=1;w for (j=2;jfk) k=j;w maxx=fk;w coutk;w k=ck;w while (k!=0) /輸出挖地雷的順序w w cout-k;w k=ck;w w coutendl;w coutmaxxendl; /輸出最多挖出的地雷數(shù)w【例【例7】友好城市友好城市 【問題描述】【問題描述】 Palmia國有一條橫貫東西的大河，河有筆直的南北兩岸，岸上各有位置各不相同的N個城市。北岸的每個城市有且僅有一個友好城市在南岸，而且不同城市的友好城市不相同。 每對友好城市都向政府申請在河上開辟一條直線航道連接兩個城市，但是由于河

41、上霧太大，政府決定避免任意兩條航道交叉，以避免事故。編程幫助政府做出一些批準(zhǔn)和拒絕申請的決定，使得在保證任意兩條航線不相交的情況下，被批準(zhǔn)的申請盡量多。【輸入格式】【輸入格式】 第1行，一個整數(shù)N(1=N=5000)，表示城市數(shù)。 第2行到第n+1行，每行兩個整數(shù)，中間用1個空格隔開，分別表示南岸和北岸的一對友好城市的坐標(biāo)。(0=xi=10000)【輸出格式】【輸出格式】 僅一行，輸出一個整數(shù)，表示政府所能批準(zhǔn)的最多申請數(shù)?！据斎霕永俊据斎霕永?7 22 4 2 6 10 3 15 12 9 8 17 17 4 2【輸出樣例】【算法分析】 我們將每對友好城市看成一條線段，則這道題的描述化為

42、：有N條線段，問最少去掉多少條線，可以使剩下的線段互不交叉？第一，以北岸為線的起點(diǎn)而南岸為線的終點(diǎn)；先將所有的線按照起點(diǎn)坐標(biāo)值從小到大排序，按照每條線的終點(diǎn)坐標(biāo)計算交叉數(shù)：求線I的交叉數(shù)AI，則檢查所有1.I-1條線，若線J( 1= J I)的終點(diǎn)值大于線I的終點(diǎn)值，則線I與線J相交。AI與AJ同時加1。整個搜索量最大為5000*5000。第二，將A數(shù)組從大到小排序，每刪除一條線，則將與之相交的線的A值減1，重復(fù)這個過程，直到所有A值都為0。此時剩下的線則全不交叉。 4如上數(shù)據(jù)，則可得下面結(jié)果：編號 南岸 北岸 交叉數(shù)11322242331244515523 此時，1、2、3航線的交叉數(shù)都一樣

43、，如果刪去的是3、5線，則剩下的1、2、4線互不相交，最多航線數(shù)為3；但如果刪去的是2、3，則還要刪去第5線才符合要求，此時的最多航線數(shù)為2，不是最優(yōu)解。 于是，我們從上面的分析中再深入，將航線按起點(diǎn)坐標(biāo)排好序后，如上所述，在本題中，只要線J的起點(diǎn)小于線I的起點(diǎn)，同時它的終點(diǎn)也小于線I的終點(diǎn)，則線J和線I不相交。因此，求所有線中最多能有多少條線不相交，實(shí)際上是從終點(diǎn)坐標(biāo)值數(shù)列中求一個最長不下降序列。這就把題目轉(zhuǎn)化為一個非常典型的動態(tài)規(guī)劃題目了。 求最長不下降序列的規(guī)劃方程如下： L(Si)=maxL(Sj)+1；1 = j i且 Sj Si。Si為航線的終點(diǎn)坐標(biāo)值。從以上分析過程可以得出：當(dāng)我

44、們拿到一道題時，不要急于求解，而應(yīng)先將題目的表面現(xiàn)象一層層象剝竹筍一樣去掉，只留下最實(shí)質(zhì)的內(nèi)容。這時再來設(shè)計算法，往往能事半功倍?！纠?】合唱隊(duì)形【問題描述】N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號為1, 2, , K，他們的身高分別為T1, T2, , TK，則他們的身高滿足T1 T2 Ti+1 TK (1iK)。你的任務(wù)是，已知所有N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形?！据斎胛募枯斎胛募horus.in的第一行是一個整數(shù)N（2 N 100），表示同

45、學(xué)的總數(shù)。第二行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti（130 Ti 230）是第i位同學(xué)的身高（厘米）。【輸出文件】輸出文件chorus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186 186 150 200 160 130 197 220【樣例輸出】4【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，保證有n 20；對于全部的數(shù)據(jù)，保證有n100?！舅惴ǚ治觥课覀儼凑沼勺蠖液陀捎叶蟮捻樞?，將n個同學(xué)的身高排成數(shù)列。如何分別在這兩個數(shù)列中尋求遞增的、未必連續(xù)的最長子序列，就成為問題的關(guān)鍵。設(shè)a 為身高序列，其中ai為同學(xué)i的身高；b 為由左而右身高遞增的人數(shù)序列，其中

46、bi為同學(xué)1同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然bi=maxbj|同學(xué)j的身高同學(xué)i的身高+1；c為由右而左身高遞增的人數(shù)序列，其中ci為同學(xué)n同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然ci=maxcj|同學(xué)j的身高同學(xué)i的身高+1；由上述狀態(tài)轉(zhuǎn)移方程可知，計算合唱隊(duì)形的問題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使bi和ci最大，子問題的解bj和ck必須最大(1ji-1 ，i+1kn)和重迭子問題的性質(zhì)(為求得bi和ci，必須一一查閱子問題的解b1bi-1和ci+1cn)，因此可采用動態(tài)程序設(shè)計的方法求解。顯然，合唱隊(duì)的人數(shù)為maxbi+ci-1(公式中同學(xué)i被重復(fù)計算，因此減

47、1)，n減去合唱隊(duì)人數(shù)即為解。具體算法如下：#include#includeusing namespace std;int a200,b200,c200;main() int n,i,j,maxx; cinn; /讀學(xué)生數(shù) memset(b,0,sizeof(b); /身高滿足遞增順序的兩個隊(duì)列初始化 memset(c,0,sizeof(c); for (i=1;iai; for (i=1;i=n;i+) /按照由左而右的順序計算b序列 bi=1; for (j=1;jaj)&(bj+1bi) bi=bj+1; wfor (i=n;i=1;i-) /按照由右而左的順序計算c序列w w ci=1

48、;w for (j=i+1;j=n;j+)w if (ajci)w ci=cj+1;w w maxx=0; /計算合唱隊(duì)的人數(shù)max（其中1人被重復(fù)計算w for (i=1;imaxx)w maxx=bi+ci;w coutn-maxx+1endl; /輸出出列人數(shù)ww這個算法的時間復(fù)雜度為O(n2)，在1秒時限內(nèi)可解決n100范圍內(nèi)的問題?！纠纠?】機(jī)器分配】機(jī)器分配【問題描述】【問題描述】總公司擁有高效設(shè)備總公司擁有高效設(shè)備M臺，準(zhǔn)備分給下屬的臺，準(zhǔn)備分給下屬的N個分公司。各分公司若獲得個分公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這這些設(shè)備，可以為國家提供一定

49、的盈利。問：如何分配這M臺設(shè)備才能使國家臺設(shè)備才能使國家得到的盈利最大？求出最大盈利值。其中得到的盈利最大？求出最大盈利值。其中M15，N10。分配原則：每個公司。分配原則：每個公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺數(shù)不超過設(shè)備數(shù)有權(quán)獲得任意數(shù)目的設(shè)備，但總臺數(shù)不超過設(shè)備數(shù)M。輸入數(shù)據(jù)文件格式為：第一行有兩個數(shù)，第一個數(shù)是分公司數(shù)輸入數(shù)據(jù)文件格式為：第一行有兩個數(shù)，第一個數(shù)是分公司數(shù)N，第二個，第二個數(shù)是設(shè)備臺數(shù)數(shù)是設(shè)備臺數(shù)M。接下來是一個接下來是一個N*M的矩陣，表明了第的矩陣，表明了第 I個公司分配個公司分配 J臺機(jī)器的盈利。臺機(jī)器的盈利?！据斎霕永俊据斎霕永縜ssigned.in3 3 /3個分公司分個分公司分3臺機(jī)器臺機(jī)器30 40 5020 30 5020 25 30【輸出樣例】【輸出樣例】assigned.out70 /最大盈利值為最大盈利值為701 1 /第一分公司分第一分公司分1臺臺2 1 /第二分公司分第二分公司分1臺臺3 1 /第三分公司分第三分公司分1臺臺【算法分析算法分析】按照公司的順序來分配機(jī)器，即按照公司的順序劃分階段，第一個階段把按照公司的順