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

1、動態(tài)規(guī)劃的優(yōu)化第1頁，共37頁，2022年，5月20日，15點18分，星期一動態(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頁，共37頁，2022年，5月20日，15點18分，星期一優(yōu)化方法1：改進(jìn)狀態(tài)的表示例1：理想收入問題理想收入是指在股票交易中，以1元為本金可能獲得的最高收入，并且在理想收入中允許有非整數(shù)股票買賣。已知股票在第i天每股價格是Vi元，1iM，求M天后的理想收入。第3頁，共37頁，2022年，5月20日，15點18分，星期一方法一設(shè)Fi表

2、示在第i天收盤時能達(dá)到的最高收入，則有Fi的遞推關(guān)系式：公式含義：在第i天收盤時能達(dá)到的最高的收入，是將第j天收盤后的收入，全部用于買入第k天的股票，再在第i天將所持的股票全部賣出所得的收入。時間復(fù)雜度是O(M3)。 第4頁，共37頁，2022年，5月20日，15點18分，星期一方法二設(shè)Pi表示前i天能獲得的最多股票數(shù)，則可列出狀態(tài)轉(zhuǎn)移方程：設(shè)Qi表示前i天能達(dá)到的最大收入，則可列出狀態(tài)轉(zhuǎn)移方程： 時間復(fù)雜度是O(M2)。第5頁，共37頁，2022年，5月20日，15點18分，星期一方法三分析：上述公式的含義是當(dāng)0=ji 時,求Qi-1和Qj*vi/vj的最大值 對于0=ji，要求Qi,實際上

3、Q1Qi-1都已經(jīng)求出，因此我們只要搞一個變量保存Qj/Vj 的最大值即可，記為MaxQ.這樣，公式可以寫成對每次求出的Qi,都更新MaxQ,顯然時間復(fù)雜度為O(M)第6頁，共37頁，2022年，5月20日，15點18分，星期一 問題描述 現(xiàn)有n首由Raucous Rockers 演唱組錄制的歌曲，計劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇： (1) 這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序； (2) 包含歌曲的總數(shù)盡可能多。 輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所

4、有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。例2 Raucous Rockers 演唱組第7頁，共37頁，2022年，5月20日，15點18分，星期一 設(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)移方程為：當(dāng)klongi，i1時：gi, j, k=maxgi-1,j,k-longi+1，gi-1,j,k當(dāng)klongi，i1時：gi, j, k=maxgi-1,j-1,t-longi+1，gi-1,j,k規(guī)劃的邊界條件為：當(dāng)0jm，

5、 0kt時：g0,j,k=0;問題的最優(yōu)解為：gn,m,0。算法的時間復(fù)雜度為：O(n*m*t)。第8頁，共37頁，2022年，5月20日，15點18分，星期一改進(jìn)的狀態(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)的計算方法為：當(dāng)b+longi t時： a=a; b=b+longi;當(dāng)b+longi t時： a=a+1; b=longi;規(guī)劃的邊界條件：當(dāng)0in時，gi,0=(0,0

6、) 題目所求的最大值是：answer=maxk| gn, k(m-1,t) 算法的時間復(fù)雜度為：O(n2)。第9頁，共37頁，2022年，5月20日，15點18分，星期一優(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頁，共37頁，2022年，5月20日，15點18分，星期一分析對方程進(jìn)行一下改進(jìn)：對于 ji,fi = maxf(j)+1, 其中，minj | r jairj為所有等于fj時aj的

7、最小值。因此，我們可以搞一個隊列維護(hù)f(j)的上升序列。對于當(dāng)前的i，利用二分查找在隊列查找到滿足條件bjbi的f(j)用bi去替換與f(i)相等的bj若bjbi，則用bi替換bj若在對尾，則直接插入顯然該算法的時間復(fù)雜度為O(n*log(n)第11頁，共37頁，2022年，5月20日，15點18分，星期一 例4：最大子序和問題描述 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這個序列的和最大。第12頁，共37頁，2022年，5月20日，15點18分，星期一最大子序和輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段長度不超過m的連續(xù)的子序

8、列，使得這個序列的和最大。例如：序列 1， -3， 5， 1， -2， 3當(dāng)M=2或3時,S=5+1=6當(dāng)M=4時,S=5+1-2+3=7數(shù)據(jù)范圍: 50%的數(shù)據(jù)N,M=1000 100%的數(shù)據(jù)N,M=20000第13頁，共37頁，2022年，5月20日，15點18分，星期一一個簡化的問題序列的最大連續(xù)和 輸入一個長度為的整數(shù)序列（A1,A2,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。 和原問題相比沒有M這個序列長度的限制！第14頁，共37頁，2022年，5月20日，15點18分，星期一 設(shè) F(i)表示以第i個數(shù)結(jié)尾的最大連續(xù)和 以第i個數(shù)結(jié)尾的最大連續(xù)和序列，可能存在兩種選擇

9、： 情形一：只包含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)分析第15頁，共37頁，2022年，5月20日，15點18分，星期一算法一枚舉設(shè) F(i)為以Ai結(jié)尾長度不超過M的最大子序和 對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復(fù)雜度為O(n2)第16頁，共37頁，2022年，5月20日，15點18分，星期一簡化方程第17頁，共37頁，2022年，5月20日，15點18分，星期一 用一個二叉堆來維護(hù)S

10、(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)從堆中取出當(dāng)前最小值.復(fù)雜度O(1) 所以計算的總復(fù)雜度為O(nlog2n)第18頁，共37頁，2022年，5月20日，15點18分，星期一隊列優(yōu)化 在算法二中，考慮用隊列來維護(hù)決策值S(i-k)。每次只需要在隊首刪掉S(i-m-1)，在隊尾添加S(i-1) 。但是取最小值操作還是需要O(n)時間復(fù)雜度的掃描。 考察在添加S(i-1)的時候，設(shè)現(xiàn)在隊尾的元素是

11、S(k)，由于ki-1，所以S(k)必然比S(i-1)先出隊。若此時S(i-1)=S(k)，則S(k)這個決策永遠(yuǎn)不會在以后用到，可以將S(k)從隊尾刪除掉（此時隊列的尾部形成了一個類似棧的結(jié)構(gòu)）第19頁，共37頁，2022年，5月20日，15點18分，星期一隊列優(yōu)化 同理，若隊列中兩個元素S(i)和S(j)，若i=S(j)，則我們可以刪掉S(i)（因為S(i)永遠(yuǎn)不會被用到）。此時的隊列中的元素構(gòu)成了一個單調(diào)遞增的序列，即：S1S2S3Sk第20頁，共37頁，2022年，5月20日，15點18分，星期一算法三 我們來整理在求F(i)的時候，用隊列維護(hù)S(i-k)所需要的操作： 若當(dāng)前隊首元素

12、S(x)，有x=i-m為止。 若當(dāng)前隊尾元素S(k)=S(i-1)，則S(k)出隊；直到S(k)S(i-1)為止。 在隊尾插入S(i-1) 取出隊列中的最小值，即隊首元素。第21頁，共37頁，2022年，5月20日，15點18分，星期一算法三 由于對于求每個F(i)的時候，進(jìn)隊和出隊的元素不止一個。 但是我們可以通過分?jǐn)偡治龅弥恳粋€元素S(i)只進(jìn)隊一次、出隊一次，所以隊列維護(hù)的時間復(fù)雜度是O(n)。而每次求F(i)的時候取最小值操作的復(fù)雜度是O(1)，所以這一步的總復(fù)雜度也是O(n)。 綜上所述，該算法的總復(fù)雜度是O(n)第22頁，共37頁，2022年，5月20日，15點18分，星期一方

13、法3：根據(jù)最優(yōu)解的性質(zhì)減少決策例5：石子合并問題 規(guī)劃的邊界條件為：mi,i=0 令si,j=k，表示合并的最優(yōu)斷開位置。 算法的時間復(fù)雜度為O(n3)。第23頁，共37頁，2022年，5月20日，15點18分，星期一猜想合并第i堆到第j堆石子的最優(yōu)斷開位置si,j要么等于i，要么等于j-1，也就是說最優(yōu)合并方案只可能是： (i) (i+1 j) 或 (i j-1) (j) 第24頁，共37頁，2022年，5月20日，15點18分，星期一證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開位置 si,j=p，且ipj-1。情況1：ti, ptp+1,j 由于ip，所以可以設(shè)q=si,p。于是最優(yōu)合并方案為

14、： (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 = mi, q+mq+1,p+mp+1,j+ti, j+tq+1,j由于qp，所以ti, ptp+1,jtq+1,j，所以F1tp+1,j 與情況1是對稱的。第25頁，共37頁，2022年，5月20日，15點18分，星期一方法4:利用貪心思想減少狀態(tài)總數(shù)例6：快餐問題Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準(zhǔn)備推出一種套餐，該套餐由A個漢堡，B個薯條和C個飲料組成

15、。價格便宜。為了提高產(chǎn)量，Peter從著名的麥當(dāng)勞公司引進(jìn)了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯條和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時間是有限的、不同的，而漢堡，薯條和飲料的單位生產(chǎn)時間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請你編一程序，計算一天中套餐的最大生產(chǎn)量。為簡單起見，假設(shè)漢堡、薯條和飲料的日產(chǎn)量不超過100個。輸入:第一行為三個不超過100的正整數(shù)A、B、C中間以一個空格分開。第二行為3個不超過100的正整數(shù)p1,p2,p3分別為漢堡，薯條和飲料的單位生產(chǎn)耗時。中間以一個空格分開。第三行為N(0=0=10)，第四行為N個不超過1

16、0000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時間，中間以一個空格分開。輸出:每天套餐的最大產(chǎn)量。 第26頁，共37頁，2022年，5月20日，15點18分，星期一分析設(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)轉(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

17、-k1)*p2) div p3 ;此算法的時間復(fù)雜度為O(N*1004), 第27頁，共37頁，2022年，5月20日，15點18分，星期一優(yōu)化在本題中，可以在動態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計算，即min100 div A，100 div B，100 div c），接著，用貪心法計算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，否則再調(diào)用動態(tài)規(guī)劃；同時，在運行動態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計算出一可行

18、解，判斷是否需進(jìn)行下一步。S3：動態(tài)規(guī)劃求解。S4：輸出。第28頁，共37頁，2022年，5月20日，15點18分，星期一貪心優(yōu)化顯然，對每條流水線，我們沒有必要將對每個時刻都進(jìn)行動態(tài)規(guī)劃，可以拿出大部分時間進(jìn)行成套生產(chǎn)，剩下一些時間進(jìn)行動態(tài)規(guī)劃這樣，顯然可以極大的減少動態(tài)規(guī)劃的狀態(tài)總數(shù)，從而節(jié)約動態(tài)規(guī)劃的計算時間。第29頁，共37頁，2022年，5月20日，15點18分，星期一例7：Hotel 有N個男人，M個女人，其中有C對夫婦要住房。現(xiàn)在有P個房子。每個房子有個費用Ci和床位Bi。住房有以下要求:1.每個房子住的人數(shù)不能超過Bi2.一個房間住了夫婦，不能再住其他人。3.不考慮夫婦情況下：

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

20、詞這三種詞性，且相同詞性的單詞互不相同。單詞的個數(shù)不超過1000，單詞的長度均不超過20。語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過5k。且已知文章是由有限個句子組成的，句子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。第34頁，共37頁，2022年，5月20日，15點18分，星期一輸入11n.tablen.baleinea.sillyn.snoopyn.sillysnoopyv.isv.isnotn.kickv.kicka.bigv.crysillysnoopyisnotbigtablebaleinekicksnoopysillycry. 輸出對應(yīng)的劃分為：sillysnoopyn isnotv biga tablen.baleinen kickv snoopyn sillya cryn.如果用下面的劃分(則多一個單詞)：sillya snoopyn isnotv biga tablen.baleinen kickv snoopyn