動態(tài)規(guī)劃專題講義-文庫吧資料
2025-07-24 12:39本頁面
【正文】 f[0]:=true。 滿足條件是 i與 j在原矩陣中相鄰 . ?試想 ,如果你不知道要排序 ,你能想到這題是用動態(tài)規(guī)劃嗎 ? 填鴨 ?武器二 :填鴨 ?這個思想帶有枚舉的感覺 .就是開個大數(shù)組 ,把代價值一個個填進去 . 硬幣問題 ? 硬幣問題（經(jīng)典問題） 就是給出 n種硬幣的面值 ,問面值 M有多少種不同的表示方法 . 動態(tài)轉移方程是 F[i]:=F[i]+F[Icost[j]].當前狀態(tài)是 i,以前狀態(tài)是 icost[j]. ? 多米諾骨牌（某題的簡化） 有 N張多米諾骨牌 ,每張的兩端有兩個數(shù)字 ,范圍在 1..6之間 .每張骨牌可以正放 ,也可以反放 .求出一種擺放的情況 ,使得所有的骨牌上端數(shù)字之和與下端數(shù)字之和的差值最小 .求出最小差值 . 多米諾骨牌 可以這么考慮這個問題 : 我們把每一個骨牌的上下差值記 下。問如何把這個凸多邊形劃分成 N2個互不相交的三角形，使得這些三角形頂點的權的乘積之和最??？ 最優(yōu)三角形劃分 ? 這一題大概搜都是十分麻煩的 ,可是這一題 Dp的話 ,比搜索要容易實現(xiàn)和容易理解得多 . ? 先得表示一下狀態(tài) ,我們用 f[i,j]表示以第 i個點開頭 ,順時針長度為 j的一塊子多邊形 .如上圖中 f[1,5]表示的子多邊形 (黑色虛線劃開 ) 最優(yōu)三角形劃分 ? 如果沒有紅色虛線的部分 ,或許你會認為決策應該是枚舉子多邊形內的兩點連線 ,然后分成兩個子多邊形 .這顯然是不行的 ,因為計算機已經(jīng)無法再表示分割出來的子多邊形了 (不能用 f[i,j]來表示了 ). 最優(yōu)三角形劃分 ? 那么我們該如何決策呢 ?尋找定量 ! ? 顯然可以發(fā)現(xiàn) ,f[i,j]表示的子多邊形有一條邊是在內部的 (黑色虛線 ),而這一條邊在該子多邊形內必定屬于某個三角形 ,因為我們選擇了該子多邊形作為一種狀態(tài) ,那么就一定存在那條虛線黑邊 ,所以一定存在所說的三角形 .于是我們枚舉這個三角形的另外一個點在子多邊形的位置 ,則可以把子問題還原到原問題 (因為該三角形把多邊形劃成了兩個可以用表示的多邊形和一個三角形 ).這些再次分割出的子多邊形就是以前狀態(tài) ,而剛才的多邊形則是當前狀態(tài) . 定量 ?其實定量的作用就是為了寫出狀態(tài)轉移方程 ,即讓人能迅速找出狀態(tài)之間的關系 (決策 ).通過定量的處理 ,當前狀態(tài)又回到了以前狀態(tài) ,選手就可以知道 ,這一題就是要用動態(tài)規(guī)劃來求解了 . 定量 ? 我們來看看剛才的一些題目的定量 . ? 交錯匹配 :一定存在最后一組交錯(這好像是廢話 ),所以枚舉這個最后的交錯的位置作為狀態(tài) ,這樣就回到以前狀態(tài) . ? 買車票 :定量 1:一定有最后一個車站(這個作為狀態(tài) )。求出該句子能有多少中不同的劃分方法 .例如 : 單詞是 ab cd a b c d 句子是 abcd 他共有 4種 完全 劃分方案 : ab/cd a/b/c/d a/b/cd ab/c/d。Tom當然希望能把所有的零件都加工完，以得到更多的加工費，但當一些零件的加工時間要求有沖突時，在某個時間內他只能選擇某種零件加工（因為他只有一臺機器），為了賺得盡量多的加工費，Tom不知如何進行取舍。由于資金有限，他只能先購買一臺加工機器。 end。 for j:=1 to 3 do {枚舉以前狀態(tài) } begin if (p[i][j]i) and (cost[i] cost[p[i][j]] + c[j]) then cost[i]:=cost[p[i][j]]+c[j]。 end。 p[i][j]:=k+1。 買車票 給定起點站和終點站還有 L1,L2,L3,C1,C2,C3，求出要從 起點到終點最少要花多少錢 . 怎么辦 買車票 當前所在的某個車站 這一題的以前狀態(tài)其實只有 3種 .即滿足 3種距離 (收費 )情況的 3個車站 .要知道這 3個車站可以先做一個預處理 .顯然這 3個車站在滿足距離限制的條件下應該越遠越好 . 買車票 ? 預處理 很容易想出一個 N^2的預處理 ,但是那樣是會超時的 .由于盡量要讓車站離得遠 (費用是一樣的啊 )因此在每種收費情況下 ,每個車站的以前狀態(tài)車站一定是遞增的序列 .這里是只要 O(N)的程序 : for j:=1 to 3 do begin k:=en1。 買車票 某兩站之間車票價格由這兩站的距離 X決定 . 當 0X=L1時，票價為 C1元 . 當 L1X=L2時，票價為 C2元 . 當 L2X=L3時，票價為 C3元 . 當兩站距離大于 L3時沒有直達票，所以有時候要買幾 次票做幾次車才行。 各站按照離 Ekaterinburg城的距離編號。 當前的狀態(tài)就是當前你枚舉到的一組交錯的后面兩個位置 .例如上圖中當前狀態(tài)是 3和 1(第一組交錯 ),枚舉他的以前狀態(tài)就有 1 1 3之前會有一個最優(yōu)值存在 ,因此可以由此得到 3 1的最優(yōu)值 . 買車票 ?買車票 (Ural1031) Ekaterinburg城到 Sverdlovsk城有直線形的鐵路線。求出這樣的一個最長的公共子串：子串中的每個字符都能在兩個原串中找到，而且每個字符的順序和原串中的順序一致。 ? 顯然這是十分能夠體現(xiàn)狀態(tài)間的聯(lián)系的題目。 ? 每個導彈有一定的高度，當前狀態(tài)就是以第 i個導彈為最后一個打的導彈。輸入導彈依次
環(huán)評公示相關推薦
鄂ICP備17016276號-1