動(dòng)態(tài)規(guī)劃的模型構(gòu)建

1、動(dòng)態(tài)規(guī)劃的模型構(gòu)建第1頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一NOIP的動(dòng)態(tài)規(guī)劃試題加分二叉樹(2003)樹型動(dòng)態(tài)規(guī)劃合唱隊(duì)形(2004)線型動(dòng)態(tài)規(guī)劃青蛙過河(2005)線型動(dòng)態(tài)規(guī)劃能量項(xiàng)鏈(2006)合并類型動(dòng)態(tài)規(guī)劃金明的預(yù)算方案(2006)資源類型動(dòng)態(tài)規(guī)劃矩陣取數(shù)游戲(2007)規(guī)則類型動(dòng)態(tài)規(guī)劃傳紙條(2008)規(guī)則類型動(dòng)態(tài)規(guī)劃星球貿(mào)易(2009) 線型動(dòng)態(tài)規(guī)劃烏龜棋(2010) 線型動(dòng)態(tài)規(guī)劃第2頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一引例：數(shù)字三角形如圖所示的數(shù)字三角形中 從第一行的數(shù)字出發(fā) 每次向左下或右下走一格，直到最后一行 要求沿途數(shù)字之和最大

2、1 3 2 4 10 1 4 3 2 20第3頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃的基本概念階段：把問題分成幾個(gè)相互聯(lián)系的有順序的幾個(gè)環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。通常一個(gè)階段包含若干狀態(tài)。決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段某狀態(tài)的選擇。策略：由開始到終點(diǎn)的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。第4頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃的基本概念狀態(tài)轉(zhuǎn)移方程：前一階段的終點(diǎn)就是后一階段的起點(diǎn)，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律

3、，稱為狀態(tài)轉(zhuǎn)移方程。目標(biāo)函數(shù)與最優(yōu)化概念：目標(biāo)函數(shù)是衡量多階段決策過程優(yōu)劣的準(zhǔn)則。最優(yōu)化概念是在一定條件下找到一個(gè)途徑，經(jīng)過按題目具體性質(zhì)所確定的運(yùn)算以后，使全過程的總效益達(dá)到最優(yōu)。第5頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一最優(yōu)化原理一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。第6頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一無后效性“過去的步驟只能通過當(dāng)前

4、狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是歷史的總結(jié)”。這條特征說明動(dòng)態(tài)規(guī)劃只適用于解決當(dāng)前決策與過去狀態(tài)無關(guān)的問題。狀態(tài)，出現(xiàn)在策略任何一個(gè)位置，它的地位相同，都可實(shí)施同樣策略，這就是無后效性的內(nèi)涵。 舉例最短路（不帶負(fù)權(quán)邊，帶負(fù)權(quán)邊）第7頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃的解題步驟劃分階段：注意階段一定要是有序的或者是可排序的，否則問題就無法求解。選擇狀態(tài)：狀態(tài)的選擇要滿足無后效性。確定決策：決策決定著狀態(tài)的轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件和取值范圍）：根據(jù)問題的性質(zhì)（求最大/最?。?，用數(shù)學(xué)方程描述狀態(tài)轉(zhuǎn)移的

5、方法和過程第8頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一編程實(shí)現(xiàn)？循環(huán)For i For j (dummy)遞歸Solve(i,j)If solved fij return fij(dummy)第9頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一數(shù)字三角形求解狀態(tài)：f(i,j)表示走到第i行j列獲得的最大值狀態(tài)轉(zhuǎn)移方程:f(i,j)=maxf(i-1,j),f(i-1,j+1)+ai,j 初始：f(0,0)=0第10頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題1：求最短距離（1）某人要從S1前往SN，其中Si至Si+1有若干種行進(jìn)方式（步行，自行車，

6、公交車，越野車，etc），分別要花費(fèi)一定的時(shí)間問最快到達(dá)的時(shí)間是多少？第11頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一分析劃分階段、選擇狀態(tài)： 到達(dá)各個(gè)不同的地點(diǎn)作為一個(gè)階段 一個(gè)階段里就一個(gè)狀態(tài) 用Fi表示從S1到達(dá)Si所需最短的時(shí)間 寫出規(guī)劃方程（包括邊界條件）： F1=0 Fi=Fi-1+Si-1到達(dá)Si所需花費(fèi)的最短時(shí)間第12頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題1：求最短距離（2）某人要從S1前往SN，其中Si至Si+1有若干種行進(jìn)方式（步行，自行車，公交車，越野車，etc），分別要花費(fèi)一定的時(shí)間，并且如果在一個(gè)地點(diǎn)選擇切換行進(jìn)方式，需要額外消

7、耗一定的時(shí)間。問最快到達(dá)的時(shí)間是多少？第13頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一分析劃分階段、選擇狀態(tài)：使用與上面一樣的方案發(fā)現(xiàn)不可行，無法解決判定是否需要切換行進(jìn)方式 加一維狀態(tài)進(jìn)行表示 用fij表示要從S1到達(dá)Si，在Si時(shí)使用的出行方式為j，所需最短的時(shí)間寫出規(guī)劃方程（包括邊界條件）第14頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一思考？必須在每個(gè)地點(diǎn)切換行進(jìn)方式？“Si至Si+1有若干種行進(jìn)方式”為“Si至Sj(ji)有若干種行進(jìn)方式”？若為任意兩點(diǎn)Si至Sj之間都有若干種行進(jìn)方式？若在切換時(shí)候需要行進(jìn)方式時(shí)須增加時(shí)間？中途經(jīng)過的地點(diǎn)不能超過X個(gè)，該

8、如何處理？若費(fèi)用為負(fù)怎么辦？第15頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一分析設(shè)f(i)表示前i個(gè)數(shù)的最長不上升序列的長度。則,f(i)=maxf(j)+1,其中j=ai這里0ji=n。顯然時(shí)間復(fù)雜度為O(n2)。上述式子的含義：找到i之前的某j，這個(gè)數(shù)不比第i個(gè)數(shù)小,對于所有的j取f(j)的最大值。 第16頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題2:求最長公共子序列給定的字符序列X=“x0，x1，xm-1”，序列Y=“y0，y1，yk-1”是X的子序列，存在X的一個(gè)嚴(yán)格遞增下標(biāo)序列，使得對所有的j=0，1，k-1，有xij = yj。例如，X=“ABC

9、BDAB”，Y=“BCDB”是X的一個(gè)子序列。給出兩個(gè)字串S1和S2，長度不超過5000.求這兩個(gè)串的最長公共子序列長度。第17頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃設(shè)f(i,j)表示S的前i位與T的前j位的最長公共子串長度。則有，時(shí)間復(fù)雜度O(n*m)第18頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一思考？給出兩個(gè)串，求最長公共子串？給定兩個(gè)字符串，求最小編輯次數(shù)使得兩個(gè)字符串相等，所謂編輯，即刪除、插入或修改某個(gè)字符。給出一個(gè)串，求最小編輯次數(shù)，使得某個(gè)串變成回文串？第19頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題3：01背包問

10、題有N件物品;第i件物品Wi公斤;第i件物品價(jià)值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？第20頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃可以按每個(gè)物品進(jìn)行規(guī)劃，同樣每種物品有選和不選兩種選擇設(shè)F(i,j)表示前i件物品載重為j的最大效益，則有1=i=N, 0=j=N初值：F(0,j)=0F(N,M)即答案顯然時(shí)間復(fù)雜度為O(NM)第21頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一思考？完全背包問題：即每個(gè)物品可取無限次。多重背包問題：第i種物品可取ni次。帶條件背包問題：取某種物品，必須取另外一種物品的限制。二維背包

11、問題：物品分為兩類，每類分別放到一個(gè)背包中。每個(gè)物品有個(gè)編號，價(jià)值最大的前提下，所取物品組成的排列字典序最小。第22頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題4：石子合并 在一園形操場四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2) 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù): 第一行為石子堆數(shù)N; 第二行為每堆石子數(shù),每兩個(gè)數(shù)之間用一空格分隔

12、.輸出數(shù)據(jù) :從第1至第N行為得分最小的合并方案. 第N+1行為空行.從N+2到2N+1行是得分最大的合并方案. 第23頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一示例第24頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24總分：62然而仔細(xì)琢磨后，發(fā)現(xiàn)更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4

13、 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24總分：61顯然，貪心法是錯(cuò)誤的。 第25頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃 用datai,j表示將從第i顆石子開始的接下來j顆石子合并所得的分值，maxi,j表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)maxi,i = 0同樣的，我們用mini,j表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：mini,j

14、= min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j)mini,i = 0這樣，我們完美地解決了這道題。時(shí)間復(fù)雜度也是O(n3)。第26頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一思考題：多邊形 多角形是一個(gè)單人玩的游戲，開始時(shí)有一個(gè)N個(gè)頂點(diǎn)的多邊形。如圖，這里N=4。每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記，每條邊上有一個(gè)“+”號或“*”號。邊從1編號到N。 第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個(gè)頂點(diǎn)V1和 V2；得到一個(gè)新的頂點(diǎn)，標(biāo)記為V1與V2通過邊E上的運(yùn)算符運(yùn)算的結(jié)果。最后，游戲中沒有邊

15、，游戲的得分為僅剩余的一個(gè)頂點(diǎn)的值。 第27頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一樣例寫一個(gè)程序，對于給定一個(gè)多邊形，計(jì)算出可能的最高得分，并且列出得到這個(gè)分?jǐn)?shù)的過程。第28頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題5：Robots 在一個(gè)n*m的棋盤內(nèi)，一些格子里有垃圾要拾撿。現(xiàn)在有一個(gè)能撿垃圾的機(jī)器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達(dá)一個(gè)點(diǎn)，就會(huì)自動(dòng)把這個(gè)點(diǎn)內(nèi)的垃圾拾掉。問：最多能拾多少垃圾。在最多的情況下，有多少種方案？請舉出一種方案來。數(shù)據(jù)范圍:n=100,m=100第29頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期

16、一舉例最多能拾5塊。有4種方法。第30頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一分析：因?yàn)橹荒芟蛴一蛘呦蛳伦?。也就是說不能走回頭路。于是考慮動(dòng)態(tài)規(guī)劃。設(shè)Fi,j表示從(1,1)點(diǎn)開始走到(i,j)的時(shí)候，最多撿了多少垃圾。Gi,j表示在fi,j最大的時(shí)候，有多少種方案。Ci,j=1表示(i,j)點(diǎn)有垃圾。Ci,j=0表示沒有。第31頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一狀態(tài)轉(zhuǎn)移方程根據(jù)(i,j)只能從(i-1,j)或者(i,j-1)走過來。于是fi,j=Maxfi-1,j,fi,j-1+ci,j.怎么求g(i,j)？可變成有向無環(huán)圖來解決。第32頁，共47頁

17、，2022年，5月20日，15點(diǎn)18分，星期一思考？兩個(gè)機(jī)器人同時(shí)撿垃圾，如何處理？三個(gè)機(jī)器人呢？若某些垃圾之間有聯(lián)系，必須同時(shí)拾撿？第33頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一免費(fèi)餡餅 SERKOI最新推出了一種叫做“免費(fèi)餡餅”的游戲。游戲在一個(gè)舞臺(tái)上進(jìn)行。舞臺(tái)的寬度為W格，天幕的高度為H格，游戲者占一格。開始時(shí)，游戲者站在舞臺(tái)的正中央，手里拿著一個(gè)托盤。游戲開始后，從舞臺(tái)天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動(dòng)去接餡餅。游戲者每秒可以向左或右移動(dòng)一格或兩格，也可以站在愿地不動(dòng)。餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時(shí)在8-308電

18、腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好到達(dá)游戲者所在的格子中，游戲者就收集到了這塊餡餅。寫一個(gè)程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分?jǐn)?shù)之和最大。第34頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一輸入數(shù)據(jù)：第一行:寬度W（199奇數(shù)）和高度H（1 100整數(shù)）接下來給出了一塊餡餅信息。由4個(gè)正整數(shù)組成，分別表示了餡餅的初始下落時(shí)刻、水平位置、下落速度、分值。游戲開始時(shí)刻為0。從1開始自左向右依次對水平方向的每格編號。輸出數(shù)據(jù)：收集到的餡餅最大分?jǐn)?shù)之和。第35頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一由上圖

19、可知，盡管下落了4個(gè)餡餅，但只能接到3個(gè)：第1時(shí)刻可以接到分值為5的餡餅第2時(shí)刻可以接到分值為3的餡餅第3時(shí)刻可以接到分值為4的餡餅因此餡餅的總分值為5+3+4=12第36頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題6：加分二叉樹給定一個(gè)中序遍歷為1,2,3,n的二叉樹每個(gè)結(jié)點(diǎn)有一個(gè)權(quán)值定義二叉樹的加分規(guī)則為：左子樹的加分 右子樹的加分根的分?jǐn)?shù)若某個(gè)樹缺少左子樹或右子樹，規(guī)定缺少的子樹加分為1。構(gòu)造符合條件的二叉樹該樹加分最大輸出其前序遍歷序列第37頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一樣例中序遍歷為1,2,3,4,5的二叉樹有很多，下圖是其中的三棵，其中

20、第三棵加分最大，為145.第38頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一分析性質(zhì)：中序遍歷是按“左-根-右”方式進(jìn)行遍歷二叉樹，因此二叉樹左孩子遍歷序列一定在根結(jié)點(diǎn)的左邊，右孩子遍歷序列一定在根結(jié)點(diǎn)的右邊！因此，假設(shè)二叉樹的根結(jié)點(diǎn)為k，那么中序遍歷為1,2,n的遍歷序列，左孩子序列為1,2,k-1，右孩子序列為k+1,k+2,n，如下圖第39頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一動(dòng)態(tài)規(guī)劃設(shè)f(i,j)中序遍歷為i,i+1,j的二叉樹的最大加分，則有： f(i,j)=maxfi,k-1*fk+1,j +dk顯然 f(i,i)=di答案為f(1,n)1=i=k

21、=j=n時(shí)間復(fù)雜度 O(n3)要構(gòu)造這個(gè)樹，只需記錄每次的決策值，令b(i,j)=k，表示中序遍歷為i,i+1,j的二叉樹的取最優(yōu)決策時(shí)的根結(jié)點(diǎn)為k最后前序遍歷這個(gè)樹即可。第40頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一思考題：選課 大學(xué)里實(shí)行學(xué)分。每門課程都有一定的學(xué)分，學(xué)生只要選修了這門課并考核通過就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門課的學(xué)分的總和。每個(gè)學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如，數(shù)據(jù)結(jié)構(gòu)必須在選修了高級語言程序設(shè)計(jì)之后才能選修。我們稱高級語言程序設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)

22、的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個(gè)課號，課號依次為1，2，3，。 每個(gè)學(xué)生可選課程的總數(shù)是給定的?，F(xiàn)在請你找出一種選課方案，使得你能得到學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)間上的沖突。第41頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一 輸入 輸入文件的第一行包括兩個(gè)正整數(shù)M、N（中間用一個(gè)空格隔開）其中M表示待選課程總數(shù)（1M1000)，N表示學(xué)生可以選的課程總數(shù)（1NM)。 以下M行每行代表一門課，課號依次為1，2M。每行有兩個(gè)數(shù)（用一個(gè)空格隔開），第一個(gè)數(shù)為這門課的先修課的課號（若不存在先修課則該項(xiàng)為0），第二個(gè)數(shù)為這門課的學(xué)分。學(xué)分是不超過10的正整數(shù)。輸出 輸出文件第一行只有一個(gè)數(shù)，即實(shí)際所選課程的學(xué)分總數(shù)。以下N行每行有一個(gè)數(shù)，表示學(xué)生所選課程的課號。第42頁，共47頁，2022年，5月20日，15點(diǎn)18分，星期一問題7：聚會(huì)的快樂你要組織一個(gè)由你公司的人參加的聚會(huì)。你希望聚會(huì)非常愉快，盡可能多地找些有趣的熱鬧。但是勸你不要同時(shí)邀請某個(gè)人和他的上司，因?yàn)檫@可能帶來爭吵。給定N個(gè)人(姓名，他幽默的系數(shù)，以及他上司