NOIP普及講座動態(tài)規(guī)劃從搜索到動態(tài)規(guī)劃

1、從搜索到動態(tài)規(guī)劃第1頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數(shù)塔問題）設(shè)有一個三角形數(shù)塔，頂點為根結(jié)點，每個結(jié)點有一個整數(shù)值。從頂點出發(fā)，能夠向左走或向右走，從根結(jié)點13出發(fā)向左、向右路徑長度能夠是：13117147，其和為521311121413，其和為63若要求從根結(jié)點開始，請找出一條路徑，使路徑之和最大,輸出路 徑長度。1315141124131211876872612第2頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數(shù)塔問題）【問題分析】（1）貪心法第3頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數(shù)塔問題）【問題分析】（2）搜索：第4頁點擊添加文本

2、點擊添加文本點擊添加文本點擊添加文本引例（數(shù)塔問題）【問題分析】（3）動態(tài)規(guī)劃： 第5頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本引例（數(shù)塔問題）1315141124131211876872612第6頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃基本概念（1）階段：把所給問題過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)絡(luò)階段，方便能按一定次序去求解。（2）狀態(tài)：狀態(tài)表示每個階段開始所處自然情況和客觀條件，它描述了研究問題過程中情況。（3）決議：決議表示當過程處于某一階段某個狀態(tài)時，能夠作出不一樣決定（或選擇），從而確定下一階段狀態(tài)，這種決定稱為決議。第7頁點擊添加文本點擊添加文本點擊添加文本

3、點擊添加文本動態(tài)規(guī)劃基本概念（4）策略和最優(yōu)策略：由全部階段決議組成決議序列稱為全過程策略，簡稱策略。 在實際問題中，從決議允許集合中找出最優(yōu)效果策略稱為最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是確定兩個相鄰階段狀態(tài)演變過程。第8頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本利用動態(tài)規(guī)劃條件（1）最優(yōu)化 子問題局部最優(yōu)將造成整個問題全局最優(yōu)，即問題含有最優(yōu)子結(jié)構(gòu)性質(zhì)。也就是說問題一個最優(yōu)解中包含著子問題一個最優(yōu)解。（2）無后效性 當前階段中狀態(tài)只能由上一個階段中狀態(tài)轉(zhuǎn)移方程得來，與其它階段狀態(tài)沒相關(guān)系，尤其是與未發(fā)生階段狀態(tài)沒相關(guān)系，這就是無后效性。 第9頁點擊添加文本點擊添加文本點擊添

4、加文本點擊添加文本動態(tài)規(guī)劃算法普通模式（1）劃分階段：按照問題時間或空間特征，把問題分為若干個階段；（2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處各種情況用不一樣狀態(tài)表示出來；（3）確定決議并寫出狀態(tài)轉(zhuǎn)移方程：普通是依據(jù)相鄰兩個階段各狀態(tài)之間關(guān)系來確定決議；（4）尋找邊界條件：給出狀態(tài)轉(zhuǎn)移方程是一個遞推式，必須有一個遞推邊界條件；（5）編寫程序。第10頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題1】攔截導彈（noi openjudge 8780）問題描述：某國為了防御敵國導彈攻擊，發(fā)展出一個導彈攔截系統(tǒng)。不過這種導彈攔截系統(tǒng)有一個缺點：即使它第一發(fā)炮彈能夠抵達任意

5、高度，不過以后每一發(fā)炮彈都不能高于前一發(fā)高度。某天，雷達捕捉到敵國導彈來襲。因為該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，所以有可能不能攔截全部導彈。輸入導彈依次飛來高度（雷達給出高度數(shù)據(jù)是小于30000正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈。第11頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解輸入第一行是一個整數(shù)N（不超出15），表示導彈數(shù)。第二行包含N個整數(shù)，為導彈依次飛來高度（雷達給出高度數(shù)據(jù)是小于30000正整數(shù)）。輸出一個整數(shù)，表示最多能攔截導彈數(shù)。樣例輸入8389 207 155 300 299 170 158 65樣例輸出6第12頁點擊添加文本點擊添加文本點擊添加文

6、本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài)： fi代表打下第i顆導彈最多能打多少顆導彈方程：fi=max(fj)+1(1=ji)且第i顆導彈高度要高于第j顆導彈高度第13頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第14頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題2】饑餓牛問題描述：牛在飼料槽前排好了隊。飼料槽依次用1到N(1=N=)編號。天天晚上，一頭幸運牛依據(jù)約翰規(guī)則，吃其中一些槽里飼料。 約翰提供B個區(qū)間清單。一個區(qū)間是一對整數(shù)start-end,1=start=end=N，表示一些連續(xù)飼料槽，比如1-3,7-8,3-4等等。牛能夠任意選擇區(qū)間，

7、不過牛選擇區(qū)間不能有重合。當然，牛希望自己能夠吃得越多越好。給出一些區(qū)間，幫助這只牛找一些區(qū)間，使它能吃到最多東西。在上面例子中，1-3和3-4是重合；聰明牛選擇1-3，7-8，這么能夠吃到5個槽里東西。第15頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【輸入格式】第一行，整數(shù)B(1=B=1000)第2到B+1行，每行兩個整數(shù)，表示一個區(qū)間，較小端點在前面【輸出格式】僅一個整數(shù)，表示最多能吃到多少個槽里食物。【樣例輸入】31 37 83 4【樣例輸出】5第16頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài)： fi代表吃了第i個區(qū)間最多能多少食物

8、方程：fi=max(fj)+i個區(qū)間長度(1=ji)且第i顆區(qū)間開始時間要大于j區(qū)間結(jié)束時間第17頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題3】最長公共子序列（codevs1408）問題描述：熊大媽奶牛在小沐沐熏陶下開始研究信息題目。小沐沐先讓奶牛研究了最長上升子序列，再讓他們研究了最長公共子序列，現(xiàn)在又讓他們要研究最長公共上升子序列了。小沐沐說，對于兩個串A，B，假如它們都包含一段位置不一定連續(xù)數(shù)字，且數(shù)字是嚴格遞增，那么稱這一段數(shù)字是兩個串公共上升子串，而全部公共上升子串中最長就是最長公共上升子串了。奶牛半懂不懂，小沐沐要你來告訴奶牛什么是最長公共上升子串。不過，

9、只要告訴奶牛它長度就能夠了。第18頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【輸入格式】第一行N，表示A，B長度。第二行，串A。第三行，串B?！据敵龈袷健枯敵鲩L度【樣例輸入】42 2 1 32 1 2 3【樣例輸出】2【數(shù)據(jù)范圍及提醒】 1=N=3000，A，B中數(shù)字不超出maxlongint第19頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài) fi,j代表a字符串到i,b字符串到j(luò)最長公共字串 方程： ai=aj 則 fi,j=fi-1,j-1+1; ai不等于aj 則fi,j=max(fi-1,j,fi,j-1)第20頁點擊添加文本點擊添

10、加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第21頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第22頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題4】最低通行費用（noi openjudge 7614）問題描述：一個商人穿過一個 N*N 正方形網(wǎng)格，去參加一個非常主要商務活動。他要從網(wǎng)格左上角進，右下角出。每穿越中間1個小方格，都要花費1個單位時間。商人必須在(2N-1)個單位時間穿越出去。而在經(jīng)過中間每個小方格時，都需要繳納一定費用。這個商人期望在要求時間內(nèi)用最少費用穿越出去。請問最少需要多少費用？注意：不能對角穿越各個小方格（即，只能向上下左右四個方向

11、移動且不能離開網(wǎng)格）。輸入第一行是一個整數(shù)，表示正方形寬度N (1 = N 100)；后面 N 行，每行 N 個小于 100 整數(shù)，為網(wǎng)格上每個小方格費用。輸出最少需要費用.第23頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解樣例輸入51 4 6 8 10 2 5 7 15 17 6 8 9 18 20 10 11 12 19 21 20 23 25 29 33 樣例輸出109提醒樣例中，最小值為109=1+2+5+7+9+12+19+21+33。第24頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài)：fi,j代表抵達i,j位置最低費用方程：fi,

12、j=max(fi-1,j,fi,j-1)+ai,j;第25頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第26頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題5】機器分配 問題描述：某總企業(yè)擁有高效生產(chǎn)設(shè)備M臺，準備分給下屬N 個分企業(yè)。各分企業(yè)若獲得這些設(shè)備，可認為總企業(yè)提供一定盈利。問：怎樣分配這 M 臺設(shè)備才能使國家得到盈利最大？求出最大盈利值。 分配標準：每個企業(yè)有權(quán)獲得任意數(shù)目標設(shè)備，但總臺數(shù)不得超過總設(shè)備數(shù) M。其中M=100，N=100。 第27頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【輸入格式】 第一行為兩個整數(shù)M，N。

13、接下來是一個NM矩陣，其中矩陣第i行第j列數(shù) Aij表明第i個企業(yè)分配j臺機器盈利。全部數(shù)據(jù)之間用一個空格分隔。 【輸出格式】 只有一個數(shù)據(jù)，為總企業(yè)分配這M臺設(shè)備所取得最大盈利。 【樣例輸入】3 2 1 2 3 2 3 4 【樣例輸出】4第28頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài)：fi,j代表前i個企業(yè)分配到j(luò)臺設(shè)備所能取得最大盈利方程fi,j=max(fi-1,j-k+ai,k) 0=k=j第29頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第30頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【例題6】復制書稿問題描

14、述： 有M本書（編號為1，2，M），每本書都有一個頁數(shù)（分別是P1，P2，PM）。想將每本都復制一份。將這M本書分給K個謄錄員（1=K=M=500)，每本書只能分配給一個謄錄員進行復制。每個謄錄員最少被分配到一本書，而且被分配到書必須是連續(xù)次序。復制工作是同時開始進行，而且每個謄錄員復制一頁書速度都是一樣。所以，復制完全部書稿所需時間取決于分配得到最多工作那個謄錄員復制時間。試找一個最優(yōu)分配方案，使分配給每一個謄錄員頁數(shù)最大值盡可能小。（假設(shè)復制一頁需要1分鐘）第31頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【輸入格式】第一行兩個整數(shù)M、K；（K=M=100）第二行M個整數(shù)

15、，第i個整數(shù)表示第i本書頁數(shù)?！据敵龈袷健抗?行，復制完全部書最少用時間（分鐘）【輸入樣例】9 31 2 3 4 5 6 7 8 9【輸出樣例】17第32頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本經(jīng)典例題講解【問題分析】狀態(tài)fi,j代筆前 i個人寫j本書所需要最少時間。方程：fi,j= min(max(fi-1,k,sj-sk) i-1=k=j-1第33頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本【程序?qū)崿F(xiàn)】第34頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃小結(jié)求得一個最優(yōu)解當前階段決議僅受前一階段決議影響，并決定下一個階段決議當前階段i多個規(guī)劃(決議)當前最優(yōu)決議當前非最優(yōu)決議i向著目標階段不停改變(動態(tài))規(guī)劃方向目標階段初始階段動態(tài)規(guī)劃第35頁點擊添加文本點擊添加文本點擊添加文本點擊添加文本動態(tài)規(guī)劃小結(jié)動態(tài)規(guī)劃和普通遞推