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

動態(tài)規(guī)劃的模型構(gòu)建第1頁，共47頁，2023年，2月20日，星期日NOIP的動態(tài)規(guī)劃試題加分二叉樹(2003)—樹型動態(tài)規(guī)劃合唱隊形(2004)—線型動態(tài)規(guī)劃青蛙過河(2005)—線型動態(tài)規(guī)劃能量項鏈(2006)—合并類型動態(tài)規(guī)劃金明的預算方案(2006)—資源類型動態(tài)規(guī)劃矩陣取數(shù)游戲(2007)—規(guī)則類型動態(tài)規(guī)劃傳紙條(2008)—規(guī)則類型動態(tài)規(guī)劃星球貿(mào)易(2009)—線型動態(tài)規(guī)劃烏龜棋(2010)—線型動態(tài)規(guī)劃第2頁，共47頁，2023年，2月20日，星期日引例：數(shù)字三角形如圖所示的數(shù)字三角形中

從第一行的數(shù)字出發(fā)

每次向左下或右下走一格，直到最后一行

要求沿途數(shù)字之和最大 132410143220第3頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃的基本概念階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。通常一個階段包含若干狀態(tài)。決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(tài)的選擇。策略：由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。第4頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃的基本概念狀態(tài)轉(zhuǎn)移方程：前一階段的終點就是后一階段的起點，前一階段的決策選擇導出了后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。目標函數(shù)與最優(yōu)化概念：目標函數(shù)是衡量多階段決策過程優(yōu)劣的準則。最優(yōu)化概念是在一定條件下找到一個途徑，經(jīng)過按題目具體性質(zhì)所確定的運算以后，使全過程的總效益達到最優(yōu)。第5頁，共47頁，2023年，2月20日，星期日最優(yōu)化原理一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。最優(yōu)化原理是動態(tài)規(guī)劃的基礎，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。第6頁，共47頁，2023年，2月20日，星期日無后效性“過去的步驟只能通過當前狀態(tài)影響未來的發(fā)展，當前的狀態(tài)是歷史的總結(jié)”。這條特征說明動態(tài)規(guī)劃只適用于解決當前決策與過去狀態(tài)無關(guān)的問題。狀態(tài)，出現(xiàn)在策略任何一個位置，它的地位相同，都可實施同樣策略，這就是無后效性的內(nèi)涵。

舉例最短路（不帶負權(quán)邊，帶負權(quán)邊）第7頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃的解題步驟劃分階段：注意階段一定要是有序的或者是可排序的，否則問題就無法求解。選擇狀態(tài)：狀態(tài)的選擇要滿足無后效性。確定決策：決策決定著狀態(tài)的轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導出本階段的狀態(tài)。寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件和取值范圍）：根據(jù)問題的性質(zhì)（求最大/最?。?，用數(shù)學方程描述狀態(tài)轉(zhuǎn)移的方法和過程第8頁，共47頁，2023年，2月20日，星期日編程實現(xiàn)？循環(huán)Fori…Forj…(dummy)遞歸Solve(i,j)Ifsolvedf[i][j]returnf[i][j](dummy)第9頁，共47頁，2023年，2月20日，星期日數(shù)字三角形求解狀態(tài)：f(i,j)表示走到第i行j列獲得的最大值狀態(tài)轉(zhuǎn)移方程: f(i,j)=max{f(i-1,j),f(i-1,j+1)}+a[i,j]

初始：f(0,0)=0第10頁，共47頁，2023年，2月20日，星期日問題1：求最短距離（1）某人要從S1前往SN，其中Si至Si+1有若干種行進方式（步行，自行車，公交車，越野車，etc），分別要花費一定的時間問最快到達的時間是多少？第11頁，共47頁，2023年，2月20日，星期日分析劃分階段、選擇狀態(tài)：

到達各個不同的地點作為一個階段

一個階段里就一個狀態(tài)

用F[i]表示從S1到達Si所需最短的時間

寫出規(guī)劃方程（包括邊界條件）：F[1]=0F[i]=F[i-1]+Si-1到達Si所需花費的最短時間第12頁，共47頁，2023年，2月20日，星期日問題1：求最短距離（2）某人要從S1前往SN，其中Si至Si+1有若干種行進方式（步行，自行車，公交車，越野車，etc），分別要花費一定的時間，并且如果在一個地點選擇切換行進方式，需要額外消耗一定的時間。問最快到達的時間是多少？第13頁，共47頁，2023年，2月20日，星期日分析劃分階段、選擇狀態(tài)：使用與上面一樣的方案發(fā)現(xiàn)不可行，無法解決判定是否需要切換行進方式

加一維狀態(tài)進行表示

用f[i][j]表示要從S1到達Si，在Si時使用的出行方式為j，所需最短的時間寫出規(guī)劃方程（包括邊界條件）第14頁，共47頁，2023年，2月20日，星期日思考？必須在每個地點切換行進方式？“Si至Si+1有若干種行進方式”為“Si至Sj(j>i)有若干種行進方式”？若為任意兩點Si至Sj之間都有若干種行進方式？若在切換時候需要行進方式時須增加時間？中途經(jīng)過的地點不能超過X個，該如何處理？若費用為負怎么辦？第15頁，共47頁，2023年，2月20日，星期日分析設f(i)表示前i個數(shù)的最長不上升序列的長度。

則, f(i)=max{f(j)+1},其中j<ianda[j]>=a[i]

這里0<j<i<=n。

顯然時間復雜度為O(n2)。上述式子的含義：找到i之前的某j，這個數(shù)不比第i個數(shù)小,對于所有的j取f(j)的最大值。

第16頁，共47頁，2023年，2月20日，星期日問題2:求最長公共子序列給定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一個嚴格遞增下標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個子序列。給出兩個字串S1和S2，長度不超過5000.求這兩個串的最長公共子序列長度。第17頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃設f(i,j)表示S的前i位與T的前j位的最長公共子串長度。則有，時間復雜度O(n*m)第18頁，共47頁，2023年，2月20日，星期日思考？給出兩個串，求最長公共子串？給定兩個字符串，求最小編輯次數(shù)使得兩個字符串相等，所謂編輯，即刪除、插入或修改某個字符。給出一個串，求最小編輯次數(shù)，使得某個串變成回文串？第19頁，共47頁，2023年，2月20日，星期日問題3：01背包問題有N件物品;第i件物品Wi公斤;第i件物品價值Ci元;現(xiàn)有一輛載重M公斤的卡車;問選取裝載哪些物品，使得卡車運送的總價值最大？第20頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃可以按每個物品進行規(guī)劃，同樣每種物品有選和不選兩種選擇設F(i,j)表示前i件物品載重為j的最大效益，則有1<=i<=N,0<=j<=N初值：F(0,j)=0F(N,M)即答案顯然時間復雜度為O(NM)第21頁，共47頁，2023年，2月20日，星期日思考？完全背包問題：即每個物品可取無限次。多重背包問題：第i種物品可取n[i]次。帶條件背包問題：取某種物品，必須取另外一種物品的限制。二維背包問題：物品分為兩類，每類分別放到一個背包中。每個物品有個編號，價值最大的前提下，所取物品組成的排列字典序最小。第22頁，共47頁，2023年，2月20日，星期日問題4：石子合并在一園形操場四周擺放N堆石子(N≤100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(≤20), (1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少(2)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大輸入數(shù)據(jù):

第一行為石子堆數(shù)N;

第二行為每堆石子數(shù),每兩個數(shù)之間用一空格分隔.輸出數(shù)據(jù):

從第1至第N行為得分最小的合并方案.第N+1行為空行.從N+2到2N+1行是得分最大的合并方案.第23頁，共47頁，2023年，2月20日，星期日示例第24頁，共47頁，2023年，2月20日，星期日N=5石子數(shù)分別為346542。用貪心法的合并過程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24總分：62然而仔細琢磨后，發(fā)現(xiàn)更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24總分：61顯然，貪心法是錯誤的。第25頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃用data[i,j]表示將從第i顆石子開始的接下來j顆石子合并所得的分值，max[i,j]表示將從第i顆石子開始的接下來j顆石子合并可能的最大值，那么：

max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<=j) max[i,i]=0同樣的，我們用min[i,j]表示將第從第i顆石子開始的接下來j顆石子合并所得的最小值，可以得到類似的方程：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)min[i,i]=0這樣，我們完美地解決了這道題。時間復雜度也是O(n3)。第26頁，共47頁，2023年，2月20日，星期日思考題：多邊形

多角形是一個單人玩的游戲，開始時有一個N個頂點的多邊形。如圖，這里N=4。每個頂點有一個整數(shù)標記，每條邊上有一個“+”號或“*”號。邊從1編號到N。第一步，一條邊被拿走；隨后各步包括如下：選擇一條邊E和連接著E的兩個頂點V1和V2；得到一個新的頂點，標記為V1與V2通過邊E上的運算符運算的結(jié)果。最后，游戲中沒有邊，游戲的得分為僅剩余的一個頂點的值。第27頁，共47頁，2023年，2月20日，星期日樣例寫一個程序，對于給定一個多邊形，計算出可能的最高得分，并且列出得到這個分數(shù)的過程。第28頁，共47頁，2023年，2月20日，星期日問題5：Robots

在一個n*m的棋盤內(nèi)，一些格子里有垃圾要拾撿?，F(xiàn)在有一個能撿垃圾的機器人從左上格子里出發(fā)，每次只能向右或者向下走。每次他到達一個點，就會自動把這個點內(nèi)的垃圾拾掉。問：最多能拾多少垃圾。在最多的情況下，有多少種方案？請舉出一種方案來。數(shù)據(jù)范圍:n<=100,m<=100第29頁，共47頁，2023年，2月20日，星期日舉例最多能拾5塊。有4種方法。第30頁，共47頁，2023年，2月20日，星期日分析：因為只能向右或者向下走。也就是說不能走回頭路。于是考慮動態(tài)規(guī)劃。設F[i,j]表示從(1,1)點開始走到(i,j)的時候，最多撿了多少垃圾。G[i,j]表示在f[i,j]最大的時候，有多少種方案。C[i,j]=1表示(i,j)點有垃圾。C[i,j]=0表示沒有。第31頁，共47頁，2023年，2月20日，星期日狀態(tài)轉(zhuǎn)移方程根據(jù)(i,j)只能從(i-1,j)或者(i,j-1)走過來。于是f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j].怎么求g(i,j)？可變成有向無環(huán)圖來解決。第32頁，共47頁，2023年，2月20日，星期日思考？兩個機器人同時撿垃圾，如何處理？三個機器人呢？若某些垃圾之間有聯(lián)系，必須同時拾撿？第33頁，共47頁，2023年，2月20日，星期日免費餡餅SERKOI最新推出了一種叫做“免費餡餅”的游戲。游戲在一個舞臺上進行。舞臺的寬度為W格，天幕的高度為H格，游戲者占一格。開始時，游戲者站在舞臺的正中央，手里拿著一個托盤。游戲開始后，從舞臺天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動去接餡餅。游戲者每秒可以向左或右移動一格或兩格，也可以站在愿地不動。餡餅有很多種，游戲者事先根據(jù)自己的口味，對各種餡餅依次打了分。同時在8-308電腦的遙控下，各種餡餅下落的速度也是不一樣的，下落速度以格/秒為單位。當餡餅在某一秒末恰好到達游戲者所在的格子中，游戲者就收集到了這塊餡餅。寫一個程序，幫助我們的游戲者收集餡餅，使得收集的餡餅的分數(shù)之和最大。第34頁，共47頁，2023年，2月20日，星期日輸入數(shù)據(jù)：

第一行:寬度W（1~99奇數(shù)）和高度H（1~100整數(shù)）

接下來給出了一塊餡餅信息。由4個正整數(shù)組成，分別表示了餡餅的

初始下落時刻、水平位置、下落速度、分值。

游戲開始時刻為0。從1開始自左向右依次對水平方向的每格編號。輸出數(shù)據(jù)：

收集到的餡餅最大分數(shù)之和。第35頁，共47頁，2023年，2月20日，星期日由上圖可知，盡管下落了4個餡餅，但只能接到3個：第1時刻可以接到分值為5的餡餅第2時刻可以接到分值為3的餡餅第3時刻可以接到分值為4的餡餅因此餡餅的總分值為5+3+4=12第36頁，共47頁，2023年，2月20日，星期日問題6：加分二叉樹給定一個中序遍歷為1,2,3,…,n的二叉樹每個結(jié)點有一個權(quán)值定義二叉樹的加分規(guī)則為：左子樹的加分×右子樹的加分＋根的分數(shù)若某個樹缺少左子樹或右子樹，規(guī)定缺少的子樹加分為1。構(gòu)造符合條件的二叉樹該樹加分最大輸出其前序遍歷序列第37頁，共47頁，2023年，2月20日，星期日樣例中序遍歷為1,2,3,4,5的二叉樹有很多，下圖是其中的三棵，其中第三棵加分最大，為145.第38頁，共47頁，2023年，2月20日，星期日分析性質(zhì)：中序遍歷是按“左-根-右”方式進行遍歷二叉樹，因此二叉樹左孩子遍歷序列一定在根結(jié)點的左邊，右孩子遍歷序列一定在根結(jié)點的右邊！因此，假設二叉樹的根結(jié)點為k，那么中序遍歷為1,2,…,n的遍歷序列，左孩子序列為1,2,…,k-1，右孩子序列為k+1,k+2,…,n，如下圖第39頁，共47頁，2023年，2月20日，星期日動態(tài)規(guī)劃設f(i,j)中序遍歷為i,i+1,…,j的二叉樹的最大加分，則有：

f(i,j)=max{f[i,k-1]*f[k+1,j]+d[k]}顯然f(i,i)=d[i]答案為f(1,n)1<=i<=k=<=j<=n時間復雜度O(n3)要構(gòu)造這個樹，只需記錄每次的決策值，令b(i,j)=k，表示中序遍歷為i,i+1,…,j的二叉樹的取最優(yōu)決策時的根結(jié)點為k最后前序遍歷這個樹即可。第40頁，共47頁，2023年，2月20日，星期日思考題：選課

大學里實行學分。每門課程都有一定的學分，學生只要選修了這門課并考核通過就能獲得相應的學分。學生最后的學分是他選修的各門課的學分的總和。每個學生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修，有些課程需要一定的基礎知識，必須在選了其它的一些課程的基礎上才能選修。例如，《數(shù)據(jù)結(jié)構(gòu)》必須在選修了《高級語言程序設計》之后才能選修。我們稱《高級語言程序設計》是《數(shù)據(jù)結(jié)構(gòu)》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。為便于表述每門課都有一個課號，課號依次為1，2，3，……。每個學生可選課程的總數(shù)是給定的?，F(xiàn)在請你找出一種選課方案，使得你能得到學分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時間上的沖突。第41頁，共47頁，2023年，2月20日，星期日

輸入輸入文件的第一行包括兩個正整數(shù)M、N（中間用一個空格隔開）其中M表示待選課程總數(shù)（1≤M≤1000)，N表示學生可以選的課程總數(shù)（1≤N≤M)。以下M行每行代表一門課，課號依次為1，2……M。每行有兩個數(shù)（用一個空格隔開），第一個數(shù)為這門課的先修課的課號（若不存在先修課則該項為0），第二個數(shù)為這門課的學分。學分是不超過10的正整數(shù)。輸出輸出文件第一行只有一個數(shù)，即實際所選課程的學分總數(shù)。以下N行每行有一個數(shù)，表示學生所選課程的課號。第42頁，共47頁，2023年，2月20日，星期日問題7：聚會的快樂你要組織一個由你公司的人參加的聚會。你希望聚會非常愉快，盡可能多地找些有趣的熱鬧。但是勸你不要同時邀請某個人和他的上司，因為這可能帶來爭吵。給定N個人(姓名，他幽默的系數(shù)，以及他上司的名字)，編程找到能使幽默系數(shù)和最大的若干個人?！据斎搿?/p>

第一行一個整