noip教程-動態(tài)規(guī)劃的優(yōu)化

1、動態(tài)規(guī)劃的優(yōu)化方法YALI 朱全民1動態(tài)規(guī)劃優(yōu)化的內(nèi)涵動態(tài)規(guī)劃算法的時間復(fù)雜度= 階段數(shù)*每個階段狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù) *每次狀態(tài)轉(zhuǎn)移的時間 或者:狀態(tài)總數(shù)*每次狀態(tài)轉(zhuǎn)移的時間重點:減少每個階段的狀態(tài)數(shù)，也就是減少了狀態(tài)總數(shù)2優(yōu)化方法1：改進狀態(tài)的表示例1：理想收入問題理想收入是指在股票交易中，以1元為本金可能獲得的最高收入，并且在理想收入中允許有非整數(shù)股票買賣。已知股票在第i天每股價格是Vi元，1iM，求M天后的理想收入。3方法一設(shè)Fi表示在第i天收盤時能達到的最高收入，則有Fi的遞推關(guān)系式：公式含義：在第i天收盤時能達到的最高的收入，是將第j天收盤后的收入，全部用于買入第k天的股票，再在第i天

2、將所持的股票全部賣出所得的收入。時間復(fù)雜度是O(M3)。 4方法二設(shè)Pi表示前i天能獲得的最多股票數(shù)，則可列出狀態(tài)轉(zhuǎn)移方程：設(shè)Qi表示前i天能達到的最大收入，則可列出狀態(tài)轉(zhuǎn)移方程： 時間復(fù)雜度是O(M2)。5方法三分析：上述公式的含義是當0=ji 時,求Qi-1和Qj*vi/vj的最大值 對于0=ji，要求Qi,實際上Q1Qi-1都已經(jīng)求出，因此我們只要搞一個變量保存Qj/Vj 的最大值即可，記為MaxQ.這樣，公式可以寫成對每次求出的Qi,都更新MaxQ,顯然時間復(fù)雜度為O(M)6 問題描述 現(xiàn)有n首由Raucous Rockers 演唱組錄制的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張

3、唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標準進行選擇： (1) 這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序； (2) 包含歌曲的總數(shù)盡可能多。 輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。例2 Raucous Rockers 演唱組7 設(shè)n首歌曲按照創(chuàng)作順序排序后的長度為long1.n，則動態(tài)規(guī)劃的狀態(tài)表示描述為： gi, j, k，(0in，0jm，0kt), 表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉(zhuǎn)移方程為：當klongi，i1時：gi

4、, j, k=maxgi-1,j,k-longi+1，gi-1,j,k當klongi，i1時：gi, j, k=maxgi-1,j-1,t-longi+1，gi-1,j,k規(guī)劃的邊界條件為：當0jm， 0kt時：g0,j,k=0;問題的最優(yōu)解為：gn,m,0。算法的時間復(fù)雜度為：O(n*m*t)。8改進的狀態(tài)表示描述為： gi,j=(a, b)，0in，0ji，0am，0bt，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。狀態(tài)轉(zhuǎn)移方程為：gi, j=mingi-1,j，gi-1,j-1+longi 其中(a, b)+longi=(a, b)的計算方法為：當b+longi

5、t時： a=a; b=b+longi;當b+longi t時： a=a+1; b=longi;規(guī)劃的邊界條件：當0in時，gi,0=(0,0) 題目所求的最大值是：answer=maxk| gn, k(m-1,t) 算法的時間復(fù)雜度為：O(n2)。9優(yōu)化方法2：利用決策的單調(diào)性例3：最長上升序列問題 f(i)=maxf(j)+1 (1=ji=n, bjbi)上式含義為：對于所有的1=ji，bjbi,必須找一個最大的f(j)反過來說，對于1=ji，必須找到一個最大的f(j),滿足bjbi。10分析對方程進行一下改進：對于 ji,fi = maxf(j)+1, 其中，minj | r jairj為

6、所有等于fj時aj的最小值。因此，我們可以搞一個隊列維護f(j)的上升序列。對于當前的i，利用二分查找在隊列查找到滿足條件bjbi的f(j)用bi去替換與f(i)相等的bj若bjbi，則用bi替換bj若在對尾，則直接插入顯然該算法的時間復(fù)雜度為O(n*log(n)11 例4：最大子序和問題描述 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這個序列的和最大。12最大子序和輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段長度不超過m的連續(xù)的子序列，使得這個序列的和最大。例如：序列 1， -3， 5， 1， -2， 3當M=2或3時,S=5+1

7、=6當M=4時,S=5+1-2+3=7數(shù)據(jù)范圍: 50%的數(shù)據(jù)N,M=1000 100%的數(shù)據(jù)N,M=2000013一個簡化的問題序列的最大連續(xù)和 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。 和原問題相比沒有M這個序列長度的限制！14設(shè) F(i)表示以第i個數(shù)結(jié)尾的最大連續(xù)和 以第i個數(shù)結(jié)尾的最大連續(xù)和序列，可能存在兩種選擇： 情形一：只包含Ai 情形二：包含Ai和以Ai-1結(jié)尾的最大連續(xù)和序列狀態(tài)轉(zhuǎn)移方程如下： F(i)=maxAi , F(i-1)+Ai邊界：F(1)=A1，Ans=maxF(i)|1=i=n該算法的時間復(fù)雜度為O(n)分

8、析15算法一枚舉設(shè) F(i)為以Ai結(jié)尾長度不超過M的最大子序和 對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復(fù)雜度為O(n2)16簡化方程17 用一個二叉堆來維護S(i-k)，每次求F(i)之前的操作如下：算法二堆求F(i-1)時，求minS(i-m-1), ,S(i-2)求F(i)時， 求minS(i-m),S(i-1)在堆中刪除元素S(i-m-1)，插入元素S(i-1).復(fù)雜度O(2log2n)從堆中取出當前最小值.復(fù)雜度O(1) 所以計算的總復(fù)雜度為O(nlog2n)18隊列優(yōu)化 在算法二中，考慮用隊列來維護決策值S(i-k)。每次只需要在隊首刪掉S(i

9、-m-1)，在隊尾添加S(i-1) 。但是取最小值操作還是需要O(n)時間復(fù)雜度的掃描。 考察在添加S(i-1)的時候，設(shè)現(xiàn)在隊尾的元素是S(k)，由于ki-1，所以S(k)必然比S(i-1)先出隊。若此時S(i-1)=S(k)，則S(k)這個決策永遠不會在以后用到，可以將S(k)從隊尾刪除掉（此時隊列的尾部形成了一個類似棧的結(jié)構(gòu)）19隊列優(yōu)化 同理，若隊列中兩個元素S(i)和S(j)，若i=S(j)，則我們可以刪掉S(i)（因為S(i)永遠不會被用到）。此時的隊列中的元素構(gòu)成了一個單調(diào)遞增的序列，即：S1S2S3Sk20算法三 我們來整理在求F(i)的時候，用隊列維護S(i-k)所需要的操作

10、： 若當前隊首元素S(x)，有x=i-m為止。 若當前隊尾元素S(k)=S(i-1)，則S(k)出隊；直到S(k)S(i-1)為止。 在隊尾插入S(i-1) 取出隊列中的最小值，即隊首元素。21算法三 由于對于求每個F(i)的時候，進隊和出隊的元素不止一個。 但是我們可以通過分攤分析得知，每一個元素S(i)只進隊一次、出隊一次，所以隊列維護的時間復(fù)雜度是O(n)。而每次求F(i)的時候取最小值操作的復(fù)雜度是O(1)，所以這一步的總復(fù)雜度也是O(n)。 綜上所述，該算法的總復(fù)雜度是O(n)22方法3：根據(jù)最優(yōu)解的性質(zhì)減少決策例5：石子合并問題 規(guī)劃的邊界條件為：mi,i=0 令si,j=k，表示

11、合并的最優(yōu)斷開位置。 算法的時間復(fù)雜度為O(n3)。23猜想合并第i堆到第j堆石子的最優(yōu)斷開位置si,j要么等于i，要么等于j-1，也就是說最優(yōu)合并方案只可能是： (i) (i+1 j) 或 (i j-1) (j) 24證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開位置 si,j=p，且ipj-1。情況1：ti, ptp+1,j 由于ip，所以可以設(shè)q=si,p。于是最優(yōu)合并方案為： (iq) (q+1.p) (p+1j) ，它的得分， F1=mi, q+mq+1,p+mp+1,j+ti, j+ti, p我們可以構(gòu)造如下的合并方案： (iq) (q+1.p) (p+1j) ，它的得分， F2 = m

12、i, q+mq+1,p+mp+1,j+ti, j+tq+1,j由于qp，所以ti, ptp+1,jtq+1,j，所以F1tp+1,j 與情況1是對稱的。25方法4:利用貪心思想減少狀態(tài)總數(shù)例6：快餐問題Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準備推出一種套餐，該套餐由A個漢堡，B個薯條和C個飲料組成。價格便宜。為了提高產(chǎn)量，Peter從著名的麥當勞公司引進了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯條和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時間是有限的、不同的，而漢堡，薯條和飲料的單位生產(chǎn)時間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請

13、你編一程序，計算一天中套餐的最大生產(chǎn)量。為簡單起見，假設(shè)漢堡、薯條和飲料的日產(chǎn)量不超過100個。輸入:第一行為三個不超過100的正整數(shù)A、B、C中間以一個空格分開。第二行為3個不超過100的正整數(shù)p1,p2,p3分別為漢堡，薯條和飲料的單位生產(chǎn)耗時。中間以一個空格分開。第三行為N(0=0=10)，第四行為N個不超過10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時間，中間以一個空格分開。輸出:每天套餐的最大產(chǎn)量。 26分析設(shè)pi,j,k表示前i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(shù)。用ri,j,k表示第i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯條的情況下最多可生產(chǎn)飲料的個數(shù)。狀態(tài)

14、轉(zhuǎn)移方程如下： pi,j,k = Maxpi-1,j1,k1+ri,j-j1,k-k1約束條件： ( 0=j1=j=100,0=k1=k=100, & (j-j1)*p1+(k-k1)*p2=Ti) ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2) div p3 ;此算法的時間復(fù)雜度為O(N*1004), 27優(yōu)化在本題中，可以在動態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計算，即min100 div A，100 div B，100 div c），接著，用貪心法計算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，

15、否則再調(diào)用動態(tài)規(guī)劃；同時，在運行動態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進行比較，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計算出一可行解，判斷是否需進行下一步。S3：動態(tài)規(guī)劃求解。S4：輸出。28貪心優(yōu)化顯然，對每條流水線，我們沒有必要將對每個時刻都進行動態(tài)規(guī)劃，可以拿出大部分時間進行成套生產(chǎn)，剩下一些時間進行動態(tài)規(guī)劃這樣，顯然可以極大的減少動態(tài)規(guī)劃的狀態(tài)總數(shù)，從而節(jié)約動態(tài)規(guī)劃的計算時間。29例7：Hotel 有N個男人，M個女人，其中有C對夫婦要住房。現(xiàn)在有P個房子。每個房子有個費用Ci和床位Bi。住房有以下要求:1.每個房子住

16、的人數(shù)不能超過Bi2.一個房間住了夫婦，不能再住其他人。3.不考慮夫婦情況下：一個房間住了男人后，不能再住女人。對女人也是一樣。問最少的費用。(n500,m500,P500,Bisize,lsize) ，那么肯定無論如何Ci/Bi最小的那些房間肯定會被選到。于是我們可以貪心在ksize,lsize的時候，給他們安排Ci/Bi最小的房間。然后再進行動態(tài)規(guī)劃。由于Bi=5.所以size=20就夠了。這樣時間復(fù)雜度就很低了。33方法4：利用恰當?shù)臄?shù)據(jù)結(jié)構(gòu)存儲狀態(tài)，減少狀態(tài)查找時間例6、LOSTCITY現(xiàn)給出一張單詞表、特定的語法規(guī)則和一篇文章：文章和單詞表中只含26個小寫英文字母az。單詞表中的單詞

17、只有名詞，動詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的個數(shù)不超過1000，單詞的長度均不超過20。語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過5k。且已知文章是由有限個句子組成的，句子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。34我們分別用v,u,a表示動詞，名詞和輔詞，給出的文章用L1.M表示，則狀態(tài)表示描述為：F(v,i)：表示將L的前i個字符劃分為以動詞結(jié)尾（當iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子

18、數(shù)與單詞數(shù)；F(u,i)：表示將L的前i個字符劃分為以名詞結(jié)尾（當iM時，可帶任意個輔詞后綴）的最優(yōu)分解方案下劃分的句子數(shù)與單詞數(shù)。狀態(tài)轉(zhuǎn)移方程為：F(v,i)=min F(u,j)+(0,1)， L(j+1.i)為動詞； F(v,j)+(0,1)， L(j+1.i)為輔詞，iM；F(u,i)=min F(u,j)+(1,1), L(j+1.i)為名詞； F(v,j)+(0,1), L(j+1.i)為名詞； F(u,j)+(0,1), L(j+1.i)為輔詞，iM；邊界條件：F(v,0)=(1,0)； F(u,0)=(, )；問題的解為：min F(v,M), F(u,M) ；35采用不同的方

19、法查找字符串的比較： 設(shè)單詞表的規(guī)模為N（N的最大值為1000） 設(shè)文章的長度為M（M的最大值為 5000）36方法5：利用四邊形不等式的性質(zhì)降維例8：郵局按照遞增順序給出一條直線上坐標互不相同的n個村莊，要求從中選擇p個村莊建立郵局，每個村莊使用離它最近的那個郵局，使得所有村莊到各自所使用的郵局的距離總和最小。試編程計算最小距離和，以及郵局建立方案。 37分析將n個村莊按坐標遞增依次編號為1.n，第i個郵局的坐標為di，wi,j表示在di,j之間建立一個郵局的最小距離和。設(shè)mi,j表示在前j個村莊建立i個郵局的最小距離和。38分析可以證明，當僅建立一個郵局時，最優(yōu)解出現(xiàn)在中位數(shù)，即設(shè)建立郵局的村莊為k 同時，令si,j=k，記錄使用前i-1個郵局的村莊數(shù)，便于在算出最小距離和之后構(gòu)造最優(yōu)建立方案。上述算法中wi,j可通過O(n)時間的預(yù)處理，在O(1)的時間內(nèi)算出，所以，該算法的狀態(tài)總數(shù)為O(n*p)，每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為O(n)，每次狀態(tài)轉(zhuǎn)移的時間為O(1)，該算法總的時間復(fù)雜度為O(p*n2)。39猜想 W滿足四邊形不等式，即證明：設(shè)y=(i+j)/2,z=(i+j)/2,下面分為兩種情形，z