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

動態(tài)規(guī)劃的優(yōu)化第一頁，共三十七頁，編輯于2023年，星期日動態(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)移的時間重點(diǎn):減少每個階段的狀態(tài)數(shù)，也就是減少了狀態(tài)總數(shù)第二頁，共三十七頁，編輯于2023年，星期日優(yōu)化方法1：改進(jìn)狀態(tài)的表示例1：理想收入問題理想收入是指在股票交易中，以1元為本金可能獲得的最高收入，并且在理想收入中允許有非整數(shù)股票買賣。已知股票在第i天每股價格是V[i]元，1≤i≤M，求M天后的理想收入。第三頁，共三十七頁，編輯于2023年，星期日方法一設(shè)F[i]表示在第i天收盤時能達(dá)到的最高收入，則有F[i]的遞推關(guān)系式：公式含義：在第i天收盤時能達(dá)到的最高的收入，是將第j天收盤后的收入，全部用于買入第k天的股票，再在第i天將所持的股票全部賣出所得的收入。時間復(fù)雜度是O(M3)。

第四頁，共三十七頁，編輯于2023年，星期日方法二設(shè)P[i]表示前i天能獲得的最多股票數(shù)，則可列出狀態(tài)轉(zhuǎn)移方程：設(shè)Q[i]表示前i天能達(dá)到的最大收入，則可列出狀態(tài)轉(zhuǎn)移方程：時間復(fù)雜度是O(M2)。第五頁，共三十七頁，編輯于2023年，星期日方法三分析：上述公式的含義是當(dāng)0<=j<i時,求Q[i-1]和Q[j]*v[i]/v[j]的最大值對于0<=j<i，要求Q[i],實(shí)際上Q[1]…Q[i-1]都已經(jīng)求出，因此我們只要搞一個變量保存Q[j]/V[j]的最大值即可，記為MaxQ.這樣，公式可以寫成對每次求出的Q[i],都更新MaxQ,顯然時間復(fù)雜度為O(M)第六頁，共三十七頁，編輯于2023年，星期日

[問題描述]

現(xiàn)有n首由RaucousRockers演唱組錄制的歌曲，計(jì)劃從中選擇一些歌曲來發(fā)行m張唱片，每張唱片至多包含t分鐘的音樂，唱片中的歌曲不能重疊。按下面的標(biāo)準(zhǔn)進(jìn)行選擇：

(1)這組唱片中的歌曲必須按照它們創(chuàng)作的順序排序；

(2)包含歌曲的總數(shù)盡可能多。輸入n，m，t，和n首歌曲的長度，它們按照創(chuàng)作順序排序，沒有一首歌超出一張唱片的長度，而且不可能將所有歌曲的放在唱片中。輸出所能包含的最多的歌曲數(shù)目。例2

RaucousRockers演唱組第七頁，共三十七頁，編輯于2023年，星期日設(shè)n首歌曲按照創(chuàng)作順序排序后的長度為long[1..n]，則動態(tài)規(guī)劃的狀態(tài)表示描述為：

g[i,j,k]，(0≤i≤n，0≤j≤m，0≤k<t),表示前i首歌曲，用j張唱片另加k分鐘來錄制，最多可以錄制的歌曲數(shù)目。狀態(tài)轉(zhuǎn)移方程為：當(dāng)k≥long[i]，i≥1時：g[i,j,k]=max{g[i-1,j,k-long[i]]+1，g[i-1,j,k]}當(dāng)k<long[i]，i≥1時：g[i,j,k]=max{g[i-1,j-1,t-long[i]]+1，g[i-1,j,k]}規(guī)劃的邊界條件為：當(dāng)0≤j≤m，0≤k<t時：g[0,j,k]=0;問題的最優(yōu)解為：g[n,m,0]。算法的時間復(fù)雜度為：O(n*m*t)。第八頁，共三十七頁，編輯于2023年，星期日改進(jìn)的狀態(tài)表示描述為：

g[i,j]=(a,b)，0≤i≤n，0≤j≤i，0≤a≤m，0≤b≤t，表示在前i首歌曲中選取j首錄制所需的最少唱片為：a張唱片另加b分鐘。狀態(tài)轉(zhuǎn)移方程為：g[i,j]=min{g[i-1,j]，g[i-1,j-1]+long[i]}其中(a,b)+long[i]=(a’,b’)的計(jì)算方法為：當(dāng)b+long[i]≤t時：a’=a;b’=b+long[i];當(dāng)b+long[i]＞t時：a’=a+1;b’=long[i];規(guī)劃的邊界條件：當(dāng)0≤i≤n時，g[i,0]=(0,0)題目所求的最大值是：answer=max{k|g[n,k]≤(m-1,t)}算法的時間復(fù)雜度為：O(n2)。第九頁，共三十七頁，編輯于2023年，星期日優(yōu)化方法2：

利用決策的單調(diào)性例3：最長上升序列問題

f(i)=max{f(j)+1}(1<=j<i<=n,bj<bi)上式含義為：對于所有的1<=j<i，bj<bi,必須找一個最大的f(j)反過來說，對于1<=j<i，必須找到一個最大的f(j),滿足bj<bi。第十頁，共三十七頁，編輯于2023年，星期日分析對方程進(jìn)行一下改進(jìn)：對于j<i,

f[i]=max{f(j)+1},其中，min{j|r[j]<a[i]}r[j]為所有等于f[j]時a[j]的最小值。因此，我們可以搞一個隊(duì)列維護(hù)f(j)的上升序列。對于當(dāng)前的i，利用二分查找在隊(duì)列查找到滿足條件bj<bi的f(j)用bi去替換與f(i)相等的bj若bj<=bi,則舍棄bi若bj>bi，則用bi替換bj若在對尾，則直接插入顯然該算法的時間復(fù)雜度為O(n*log(n))第十一頁，共三十七頁，編輯于2023年，星期日例4：最大子序和問題描述輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的長度不超過M的子序列，使得這個序列的和最大。第十二頁，共三十七頁，編輯于2023年，星期日最大子序和輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段長度不超過m的連續(xù)的子序列，使得這個序列的和最大。例如：序列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<=1000100%的數(shù)據(jù)N,M<=20000第十三頁，共三十七頁，編輯于2023年，星期日一個簡化的問題[序列的最大連續(xù)和]

輸入一個長度為ｎ的整數(shù)序列（A1,A2,……,An），從中找出一段連續(xù)的子序列，使得這個序列的和最大。和原問題相比沒有M這個序列長度的限制！第十四頁，共三十七頁，編輯于2023年，星期日

設(shè)F(i)表示以第i個數(shù)結(jié)尾的最大連續(xù)和以第i個數(shù)結(jié)尾的最大連續(xù)和序列，可能存在兩種選擇：情形一：只包含Ai

情形二：包含Ai和以Ai-1結(jié)尾的最大連續(xù)和序列狀態(tài)轉(zhuǎn)移方程如下：

F(i)=max{Ai,F(i-1)+Ai}邊界：F(1)=A1，Ans=max{F(i)|1<=i<=n}該算法的時間復(fù)雜度為O(n)分析第十五頁，共三十七頁，編輯于2023年，星期日算法一——枚舉設(shè)

F(i)為以Ai結(jié)尾長度不超過M的最大子序和對于每個F(i)，從1到m枚舉k的值，完成Aj的累加和取最大值。該算法的時間復(fù)雜度為O(n2)第十六頁，共三十七頁，編輯于2023年，星期日簡化方程第十七頁，共三十七頁，編輯于2023年，星期日用一個二叉堆來維護(hù)S(i-k)，每次求F(i)之前的操作如下：算法二——堆求F(i-1)時，求min{S(i-m-1),……,S(i-2)}求F(i)時，求min{S(i-m),……,S(i-1)}☆在堆中刪除元素S(i-m-1)，插入元素S(i-1).復(fù)雜度O(2log2n)☆從堆中取出當(dāng)前最小值.復(fù)雜度O(1)所以計(jì)算的總復(fù)雜度為O(nlog2n)第十八頁，共三十七頁，編輯于2023年，星期日隊(duì)列優(yōu)化在算法二中，考慮用隊(duì)列來維護(hù)決策值S(i-k)。每次只需要在隊(duì)首刪掉S(i-m-1)，在隊(duì)尾添加S(i-1)。但是取最小值操作還是需要O(n)時間復(fù)雜度的掃描。考察在添加S(i-1)的時候，設(shè)現(xiàn)在隊(duì)尾的元素是S(k)，由于k<i-1，所以S(k)必然比S(i-1)先出隊(duì)。若此時S(i-1)<=S(k)，則S(k)這個決策永遠(yuǎn)不會在以后用到，可以將S(k)從隊(duì)尾刪除掉（此時隊(duì)列的尾部形成了一個類似棧的結(jié)構(gòu)）第十九頁，共三十七頁，編輯于2023年，星期日隊(duì)列優(yōu)化同理，若隊(duì)列中兩個元素S(i)和S(j)，若i<j且S(i)>=S(j)，則我們可以刪掉S(i)（因?yàn)镾(i)永遠(yuǎn)不會被用到）。此時的隊(duì)列中的元素構(gòu)成了一個單調(diào)遞增的序列，即：S1<S2<S3<……<Sk第二十頁，共三十七頁，編輯于2023年，星期日算法三我們來整理在求F(i)的時候，用隊(duì)列維護(hù)S(i-k)所需要的操作：☆若當(dāng)前隊(duì)首元素S(x)，有x<i-m，則S(x)出隊(duì)；直到隊(duì)首元素S(x)有x>=i-m為止?！钊舢?dāng)前隊(duì)尾元素S(k)>=S(i-1)，則S(k)出隊(duì)；直到S(k)<S(i-1)為止?！钤陉?duì)尾插入S(i-1)☆取出隊(duì)列中的最小值，即隊(duì)首元素。第二十一頁，共三十七頁，編輯于2023年，星期日算法三由于對于求每個F(i)的時候，進(jìn)隊(duì)和出隊(duì)的元素不止一個。但是我們可以通過分?jǐn)偡治龅弥?，每一個元素S(i)只進(jìn)隊(duì)一次、出隊(duì)一次，所以隊(duì)列維護(hù)的時間復(fù)雜度是O(n)。而每次求F(i)的時候取最小值操作的復(fù)雜度是O(1)，所以這一步的總復(fù)雜度也是O(n)。綜上所述，該算法的總復(fù)雜度是O(n)第二十二頁，共三十七頁，編輯于2023年，星期日方法3：根據(jù)最優(yōu)解的性質(zhì)減少決策例5：石子合并問題規(guī)劃的邊界條件為：m[i,i]=0

令s[i,j]=k，表示合并的最優(yōu)斷開位置。算法的時間復(fù)雜度為O(n3)。第二十三頁，共三十七頁，編輯于2023年，星期日猜想合并第i堆到第j堆石子的最優(yōu)斷開位置s[i,j]要么等于i，要么等于j-1，也就是說最優(yōu)合并方案只可能是：

{(i)(i+1…j)}

或

{(i…j-1)(j)}第二十四頁，共三十七頁，編輯于2023年，星期日證明：設(shè)合并第i堆到第j堆石子的最優(yōu)斷開位置s[i,j]=p，且i<p<j-1。情況1：t[i,p]≤t[p+1,j]

由于i<p，所以可以設(shè)q=s[i,p]。于是最優(yōu)合并方案為：

{[(i…q)(q+1...p)](p+1…j)}，它的得分，

F1=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[i,p]我們可以構(gòu)造如下的合并方案：

{(i…q)[(q+1...p)(p+1…j)]}，它的得分，

F2=m[i,q]+m[q+1,p]+m[p+1,j]+t[i,j]+t[q+1,j]由于q<p，所以t[i,p]≤t[p+1,j]<t[q+1,j]，所以F1<F2。這與合并第i堆到第j堆石子的最優(yōu)斷開位置s[i,j]=p矛盾情況2：t[i,p]>t[p+1,j]與情況1是對稱的。第二十五頁，共三十七頁，編輯于2023年，星期日方法4:利用貪心思想減少狀態(tài)總數(shù)例6：快餐問題Peter最近在R市開了一家快餐店，為了招攬顧客，該快餐店準(zhǔn)備推出一種套餐，該套餐由A個漢堡，B個薯?xiàng)l和C個飲料組成。價格便宜。為了提高產(chǎn)量，Peter從著名的麥當(dāng)勞公司引進(jìn)了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡，薯?xiàng)l和飲料，由于每條生產(chǎn)線每天所能提供的生產(chǎn)時間是有限的、不同的，而漢堡，薯?xiàng)l和飲料的單位生產(chǎn)時間又不同。這使得Peter很為難，不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請你編一程序，計(jì)算一天中套餐的最大生產(chǎn)量。為簡單起見，假設(shè)漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過100個。輸入:第一行為三個不超過100的正整數(shù)A、B、C中間以一個空格分開。第二行為3個不超過100的正整數(shù)p1,p2,p3分別為漢堡，薯?xiàng)l和飲料的單位生產(chǎn)耗時。中間以一個空格分開。第三行為N(0<=0<=10)，第四行為N個不超過10000的正整數(shù)，分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時間，中間以一個空格分開。輸出:每天套餐的最大產(chǎn)量。第二十六頁，共三十七頁，編輯于2023年，星期日分析設(shè)p[i,j,k]表示前i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯?xiàng)l的情況下最多可生產(chǎn)飲料的個數(shù)。用r[i,j,k]表示第i條生產(chǎn)線生產(chǎn)j個漢堡，k個薯?xiàng)l的情況下最多可生產(chǎn)飲料的個數(shù)。狀態(tài)轉(zhuǎn)移方程如下：

p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}約束條件：

(0<=j1<=j<=100,0<=k1<=k<=100,&&(j-j1)*p1+(k-k1)*p2<=T[i])r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的時間復(fù)雜度為O(N*1004),第二十七頁，共三十七頁，編輯于2023年，星期日優(yōu)化在本題中，可以在動態(tài)規(guī)劃方法中加入了貪心算法思想：即首先計(jì)算出每天生產(chǎn)套數(shù)的上限值（由A,B,C計(jì)算，即min｛100divA，100divB，100divc｝），接著，用貪心法計(jì)算出這N條流水線可以生產(chǎn)的套數(shù)，并與上限比較，大于則輸出上限值并退出，否則再調(diào)用動態(tài)規(guī)劃；同時，在運(yùn)行動態(tài)規(guī)劃的過程中，也可以每完成一階段工作便與上限值進(jìn)行比較，這樣以來，便可望在動態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計(jì)為：S1：讀入數(shù)據(jù)。S2：貪心求上限并計(jì)算出一可行解，判斷是否需進(jìn)行下一步。S3：動態(tài)規(guī)劃求解。S4：輸出。第二十八頁，共三十七頁，編輯于2023年，星期日貪心優(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ī)劃的計(jì)算時間。第二十九頁，共三十七頁，編輯于2023年，星期日例7：Hotel有N個男人，M個女人，其中有C對夫婦要住房?，F(xiàn)在有P個房子。每個房子有個費(fèi)用Ci和床位Bi。住房有以下要求:1.每個房子住的人數(shù)不能超過Bi2.一個房間住了夫婦，不能再住其他人。3.不考慮夫婦情況下：一個房間住了男人后，不能再住女人。對女人也是一樣。問最少的費(fèi)用。(n<500,m<500,P<500,Bi<=5)。第三十頁，共三十七頁，編輯于2023年，星期日先考慮夫婦這個限制事實(shí)上我們可以發(fā)現(xiàn)按照第2條住房的夫婦數(shù)不會超過1。如果有2對夫婦那么可以交換一下，在同樣代價下反而能住更多人。所以我們可以枚舉夫婦數(shù)，這樣就去掉了夫婦的這個限制。第三十一頁，共三十七頁，編輯于2023年，星期日考慮動態(tài)規(guī)劃設(shè)F[i,j,k]表示當(dāng)前1-i這些房間安排好后，還剩下j男k女的最小費(fèi)用。很容易寫出狀態(tài)轉(zhuǎn)移方程：F[i,j,k]=Min{f[i-1,j,k],f[i-1,j+b[i],k]+c[i],f[i-1,j,k+b[i]]+c[i]}但是這個動態(tài)規(guī)劃的時間復(fù)雜度太高了。第三十二頁，共三十七頁，編輯于2023年，星期日考慮優(yōu)化如果人數(shù)很多的話(k>size,l>size)，那么肯定無論如何Ci/Bi最小的那些房間肯定會被選到。于是我們可以貪心在k>size,l>size的時候，給他們安排Ci/Bi最小的房間。然后再進(jìn)行動態(tài)規(guī)劃。由于Bi<=5.所以size=20就夠了。這樣時間復(fù)雜度就很低了。第三十三頁，共三十七頁，編輯于2023年，星期日方法4：利用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)存儲狀態(tài)，減少狀態(tài)查找時間例6、LOSTCITY現(xiàn)給出一張單詞表、特定的語法規(guī)則和一篇文章：文章和單詞表中只含26個小寫英文字母a…z。單詞表中的單詞只有名詞，動詞和輔詞這三種詞性，且相同詞性的單詞互不相同。單詞的個數(shù)不超過1000，單詞的長度均不超過20。語法規(guī)則可簡述為：名詞短語：任意個輔詞前綴接上一個名詞；動詞短語：任意個輔詞前綴接上一個動詞；句子：以名詞短語開頭，名詞短語與動詞短語相間連接而成。文章的長度不超過5k。且已知文章是由有限個句子組成的，句子只包含有限個單詞。編程將這篇文章劃分成最少的句子，在此前提之下，要求劃分出的單詞數(shù)最少。第三十四頁，共三十七頁，編輯于2023年，星期日輸入11n.tablen.baleinea.sillyn.snoopyn.sillysnoopyv.isv.isnotn.kickv.kicka.bigv.crysillysnoopyisnotbigtablebaleinekicksnoopysillycry.

輸出對應(yīng)的劃分為：sillysnoopynisnotvbigatablen.baleinenkickvsnoopynsillyacryn.如果用下面的劃分(則多一個單詞)：sillyasnoopynisnotvbigatablen.baleinenkickvsnoopynsillyacr