樹狀DP與狀態(tài)壓縮DP課件

陳益波

香港城市大學(xué)

2011年7月30日華中科大2011ACM暑期集訓(xùn)

動態(tài)規(guī)劃（三）狀態(tài)壓縮DP及樹型DP陳益波

香港城市大學(xué)

2011年7月30日華中科大2011個人簡介祖籍：浙江香港城市大學(xué)商學(xué)院09級PhD管理科學(xué)專業(yè)OperationResearch.QQ:112997821人人網(wǎng):陳益波Email:chenyibo1029@gmail.com個人簡介主要內(nèi)容狀態(tài)壓縮思想狀態(tài)壓縮DP例題講解樹型DP特征樹型DP例題講解總結(jié)主要內(nèi)容狀態(tài)壓縮思想內(nèi)容來源樹型動態(tài)規(guī)劃和狀態(tài)壓縮動態(tài)規(guī)劃---wangfangbob動態(tài)規(guī)劃的狀態(tài)方程——樹形動態(tài)規(guī)劃，狀態(tài)壓縮，結(jié)果與參數(shù)的互換

---李子星樹型動態(tài)規(guī)劃的實例分析---李彥亭內(nèi)容來源樹型動態(tài)規(guī)劃和狀態(tài)壓縮動態(tài)規(guī)劃---wangfa什么是樹型動態(tài)規(guī)劃顧名思義，樹型動態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動態(tài)規(guī)劃，平時作的動態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個方向：根—>葉：不過這種動態(tài)規(guī)劃在實際的問題中運用的不多，也沒有比較明顯的例題，所以不在今天討論的范圍之內(nèi)。葉－>根：既根的子節(jié)點傳遞有用的信息給根，完后根得出最優(yōu)解的過程。這類的習(xí)題比較的多，下面就介紹一些這類題目和它們的一般解法。什么是樹型動態(tài)規(guī)劃顧名思義，樹型動態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)例題一：HDU2412PARTYATHALI-BULA題目大意：n個人形成一個關(guān)系樹，每個節(jié)點代表一個人，節(jié)點的根表示這個人的唯一的直接上司，只有根沒有上司。要求選取一部分人出來，使得每2個人之間不能有直接的上下級的關(guān)系，求最多能選多少個人出來，并且求出獲得最大人數(shù)的選人方案是否唯一。這是一個經(jīng)典的樹型動態(tài)規(guī)劃。狀態(tài)？轉(zhuǎn)移？例題一：HDU2412PARTYATHALI-BUL1.2PARTYATHALI-BULA簡單的染色統(tǒng)計是不正確的1.2PARTYATHALI-BULA簡單的染色統(tǒng)計1.3PARTYATHALI-BULA人之間的關(guān)系形成樹型結(jié)構(gòu)DP,用dp[i][0]表示不選擇i點時，i點及其子樹能選出的最多人數(shù)，dp[i][1]表示選擇i點時，i點及其子樹的最多人數(shù)。1.3PARTYATHALI-BULA人之間的關(guān)系形成1.4PARTYATHALI-BULA狀態(tài)轉(zhuǎn)移方程:對于葉子節(jié)點dp[k][0]=0,dp[k][1]=1對于非葉子節(jié)點i,dp[i][0]=∑max(dp[j][0],dp[j][1])(j是i的兒子)dp[i][1]=1+∑dp[j][0](j是i的兒子)最多人數(shù)即為max(dp[0][0],dp[0][1])如何判斷最優(yōu)解是否唯一?1.4PARTYATHALI-BULA狀態(tài)轉(zhuǎn)移方程:1.5PARTYATHALI-BULA新加一個狀態(tài)dup[i][j]，表示相應(yīng)的dp[i][j]是否是唯一方案。對于葉子結(jié)點,dup[k][0]=dup[k][1]=1.對于非葉子結(jié)點,對于i的任一兒子j，若(dp[j][0]>dp[j][1]且dup[j][0]==0)或(dp[j][0]<dp[j][1]且dup[j][1]==0)或(dp[j][0]==dp[j][1])，則dup[i][0]=0對于i的任一兒子j有dup[j][0]=0,則dup[i][1]=01.5PARTYATHALI-BULA新加一個狀態(tài)du例題二：STRATEGICGAME題目大意：一城堡的所有的道路形成一個n個節(jié)點的樹，如果在一個節(jié)點上放上一個士兵，那么和這個節(jié)點相連的邊就會被看守住，問把所有邊看守住最少需要放多少士兵。典型的樹型動態(tài)規(guī)劃狀態(tài)？轉(zhuǎn)移？例題二：STRATEGICGAME題目大意：2.2STRATEGICGAMEdproot[i]表示以i為根的子樹，在i上放置一個士兵，看守住整個子樹需要多少士兵。all[i]表示看守住整個以i為根的子樹需要多少士兵。2.2STRATEGICGAMEdproot[i]表2.3STRATEGICGAME狀態(tài)轉(zhuǎn)移方程：葉子節(jié)點：dproot[k]=1；all[k]=0；非葉子節(jié)點：

dproot[i]=1+∑all[j](j是i的兒子)；

all[i]=min(dproot[i],∑dproot[j](j是i的兒子));這個題目還是比較簡單的，如果把題目中看守邊變成看守相鄰的點呢？留給你來思考^_^2.3STRATEGICGAME狀態(tài)轉(zhuǎn)移方程：例題三加分二叉樹

設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分?jǐn)?shù)（均為正整數(shù)），記第i個節(jié)點的分?jǐn)?shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：subtree的左子樹的加分×subtree的右子樹的加分＋subtree的根的分?jǐn)?shù)

若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分?jǐn)?shù)。不考慮它的空子樹。

試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。例題三加分二叉樹

設(shè)一個n個節(jié)點的二叉樹tree的3.2基礎(chǔ)回顧樹的中序遍歷若二叉樹為空則結(jié)束返回，否則：（1）中序遍歷左子樹。（2）訪問根結(jié)點。（3）中序遍歷右子樹。樹的前序遍歷若二叉樹為空則結(jié)束返回，否則：（1）訪問根結(jié)點.

（2）前序遍歷左子樹.（3）前序遍歷右子樹

.3.2基礎(chǔ)回顧樹的中序遍歷3.3樣例【輸入格式】

第1行：一個整數(shù)n（n＜30），為節(jié)點個數(shù)。

第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分?jǐn)?shù)（分?jǐn)?shù)＜100）。

【輸出格式】

第1行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。

第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷。

【輸入樣例】5571210

【輸出樣例】145312453.3樣例【輸入格式】3.4分析本題適合用動態(tài)規(guī)劃來解。如果用數(shù)組value[i,j]表示從節(jié)點i到節(jié)點j所組成的二叉樹的最大加分，則動態(tài)方程可以表示如下：value[i,j]=max{value[i,i]+value[i+1,j],value[k,k]+value[i,k]*value[k+1,j]|i<k<j,value[i,j-1]+value[j,j]};第一項為左子樹為空，根為i，右子樹[i+1,j]。第二項為左子樹為i,根為i+1,右子樹為[i+2,j].3.4分析本題適合用動態(tài)規(guī)劃來解。如果用數(shù)組value[i樹型動態(tài)規(guī)劃總結(jié)必要條件：子樹之間不可以相互干擾，如果本來是相互干擾的，那么我們必須添加變量使得他們不相互干擾。樹形動態(tài)規(guī)劃通常從葉節(jié)點（邊界）開始逐步向上一層的節(jié)點（即父節(jié)點）進行狀態(tài)方程的轉(zhuǎn)移，直到根節(jié)點。樹型動態(tài)規(guī)劃總結(jié)內(nèi)容二

狀態(tài)壓縮動態(tài)規(guī)劃狀態(tài)壓縮動態(tài)規(guī)劃：用盡量少的狀態(tài)表示出DP的整個過程。壓縮所有不必要的信息。典型方式：當(dāng)需要表示一個集合有哪些元素時，往往利用2進制用一個整數(shù)表示。內(nèi)容二狀態(tài)壓縮動態(tài)規(guī)劃狀態(tài)壓縮動態(tài)規(guī)劃：例題四：經(jīng)典問題TSP一個n個點的帶權(quán)的有向圖，求一條路徑，使得這條路經(jīng)過每個點恰好一次，并且路徑上邊的權(quán)值和最?。ɑ蛘咦畲螅??；蛘咔笠粭l具有這樣性質(zhì)的回路，這是經(jīng)典的TSP問題。n<=16(重要條件,狀態(tài)壓縮的標(biāo)志)狀態(tài)？轉(zhuǎn)移？例題四：經(jīng)典問題TSP一個n個點的帶權(quán)的有向圖，求一條路徑，4.2TSP如何表示一個點集：由于只有16個點，所以我們用一個整數(shù)表示一個點集：例如：

5＝0000000000000101；（2進制表示）它的第0位和第2位是1，就表示這個點集里有2個點，分別是點0和點2。

31＝0000000000011111；（2進制表示）表示這個點集里有5個點，分別是0，1，2，4，5；4.2TSP如何表示一個點集：4.3TSP所以一個整數(shù)i就表示了一個點集；整數(shù)i可以表示一個點集，也可以表示是第i個點。狀態(tài)表示：dp[i][j]表示經(jīng)過點集i中的點恰好一次，不經(jīng)過其它的點，并且以j點為終點的路徑,權(quán)值和的最小值，如果這個狀態(tài)不存在，就是無窮大。4.3TSP所以一個整數(shù)i就表示了一個點集；4.4TSP狀態(tài)轉(zhuǎn)移：單點集：狀態(tài)存在dp[1<<j][j]=0；否則無窮大。非單點集：狀態(tài)存在dp[i][j]=min(dp[k][s]+w[s][j])k表示i集合中去掉了j點的集合，s遍歷集合k中的點并且dp[k][s]狀態(tài)存在，點s到點j有邊存在，w[s][j]表示邊的權(quán)值。狀態(tài)不存在dp[i][j]為無窮大。4.4TSP狀態(tài)轉(zhuǎn)移：4.5TSP最后的結(jié)果是：

min(dp[(1<<n)–1][j])(0<=j<n)；技巧：利用2進制，使得一個整數(shù)表示一個點集，這樣集合的操作可以用位運算來實現(xiàn)。例如從集合i中去掉點j：

k=i&(~(1<<j))或者

k=i-(1<<j)4.5TSP最后的結(jié)果是：例題五：走道鋪磚問題題意：給定一個n*m，(n,m<=20)的走道（因為是走道，所以寬度很小，但長度可能很長，保證n*m為偶數(shù)），問用1*2的磚塊鋪滿這個走道的方案數(shù)有多少。（不用考慮翻轉(zhuǎn)旋轉(zhuǎn)相同的問題，即求的不是本質(zhì)不同解的數(shù)目。）狀態(tài)？轉(zhuǎn)移？例題五：走道鋪磚問題題意：給定一個n*m，(n,m<=20)5.2走道鋪磚問題方法：用f[i,j]表示從第1行鋪到第i行，前i-1行已經(jīng)全部鋪滿，且第i行沒有橫著放的磚，且第i行的鋪磚狀態(tài)為j的二進制數(shù)對應(yīng)的狀態(tài)，的鋪磚方案總數(shù)。101011第i行用f[i,43]表示藍(lán)色部分已經(jīng)確定了的所有鋪磚方案數(shù)5.2走道鋪磚問題方法：101011第可以很容易得聯(lián)想到用f[i-1,0..2m-1]推出f[i,0..2m-1]的思路：f[i,j]=sum{f[i-1,x]|0<=x<2m且x&j=0且db(2m-1-x-j))}x中為1的數(shù)位與j中為1的數(shù)位全部不相同，且x和j都沒有填的位置一定可以只用橫著的磚蓋滿（db函數(shù)就是用來做這個判定的，可以預(yù)先將0..2m-1的db值都求出來并保存在數(shù)組中）funcdb(x):whilex>0dobegina=lowbit(x);x-=lowbit(x);If(x=0)returnfalse;b=lowbit(x);x-=lowbit(x);If(b>a*2)returnfalse;endreturntrue5.3走道鋪磚問題0011011110中的所有1就可以用橫著的磚蓋滿，而00111010就不行。判定可以利用lowbit，每輪取走兩位lowbit，如果后取的不是先取的值的兩倍，說明兩次取的不是相鄰的數(shù)位。可以很容易得聯(lián)想到用f[i-1,0..2m-1]推出f[i,5.4走道鋪磚問題最后的結(jié)果就是：sum{f[n,x]|0<=x<2m且db(2m-1-x)}計算的時間復(fù)雜度則是O(n*22m)。實際上把f的狀態(tài)轉(zhuǎn)移方程稍微變一下形式：f[i,j]=sum{f[i-1,2m-1-x-j] |0<=x<2m且db(x)且x&j=0)}就可以發(fā)現(xiàn)，x完全不需要從0一直枚舉到2m，只需要枚舉有限的若干項在0到2m范圍內(nèi)能通過db判定的x就可以了。5.4走道鋪磚問題最后的結(jié)果就是：5.5走道鋪磚問題最后的結(jié)果就是：sum{f[n,2m-1-x]|0<=x<2m且db(x)}計算的時間復(fù)雜度則是O(n*y2)，其中y=count{x|0<=x<2m且db(x)}利用排列組合的原理還可以知道：y=C(m-1,1)+C(m-2,2)+…+C(m-m/2,m/2)當(dāng)m=10時，y=78，可見其大大小于2m。5.5走道鋪磚問題最后的結(jié)果就是：5.6走道鋪磚問題走道鋪磚類似的題也非常多，比如炮兵布陣問題。還比如本題可以這樣改動：磚塊不再是1*2這一種規(guī)格了，而是有多種占地不超過3*3的磚（像俄羅斯方塊）；也不再是求鋪滿走道的方案數(shù)了，而是告訴每種規(guī)格的磚的美觀值，問能放下的磚的美觀值的總和的極大值。不同的變化常常就是進制可能變一下，比如用三進制或四進制來描述狀態(tài)。X進制也不僅僅是描述某種排布狀態(tài)，也可能描述一個集合的狀況。5.6走道鋪磚問題走道鋪磚類似的題也非常多，比如炮兵布陣問*5.7走道鋪磚其它解法F[i][k][j],輪廓線表示法，表示第i-1行已經(jīng)全部鋪滿，并且第i行的前k格也已前部鋪滿，第i+1行的前0到k-1格及第i行的k到m-1格凸出來的格子全為豎著放（對應(yīng)2制制數(shù)為j)時的方案數(shù)。轉(zhuǎn)移？*5.7走道鋪磚其它解法F[i][k][j],輪廓線表示*5.8走道鋪磚輪廓線法f[0][m][j]=0或1(由j能否擺得出決定);//整個DP初始f[i][0][j]=f[i-1][m][j];//i>0的轉(zhuǎn)移初始其它轉(zhuǎn)移？*5.8走道鋪磚輪廓線法f[0][m][j]=0或1(*5.9其它轉(zhuǎn)移,K>0,j的第k-1位為0If(j的k-2位不為0）f[i][k][j]=f[i][k-1][j^(1<<(k-1))]Else//j的k-2位也為0f[i][k][j]=f[i][k-1][j^(1<<(k-1))]+f[i][k-2][j];*5.9其它轉(zhuǎn)移,K>0,j的第k-1位為0*5.10其它轉(zhuǎn)移,K>0,j的第k-1位為1F[i][k][j]=f[i][k-1][j^(1<<(k-1))];*5.10其它轉(zhuǎn)移,K>0,j的第k-1位為15.11轉(zhuǎn)移代碼//初始化dp[0][m][j]=1，如果j可以擺得出，否則dp[0][m][j]=0;for(inti=1;i<n;i++){for(intj=0;j<(1<<m);j++)//k=0dp[i][0][j]=dp[i-1][m][j];for(intj=0;j<(1<<m);j++)//k=1dp[i][1][j]=dp[i][0][j^1];for(intk=2;k<=m;k++){//k=2,3,...,m;for(intj=0;j<(1<<m);j++){dp[i][k][j]=dp[i][k-1][j^(1<<(k-1))];if((j&(1<<(k-1)))==0&&(j&(1<<(k-2)))==0)dp[i][k][j]+=dp[i][k-2][j];}}}最終答案為dp[n-1][m][0]的值5.11轉(zhuǎn)移代碼//初始化dp[0][m][j思考題：方格選數(shù)最大HDU2167

題目大意：You'regivenanunlimitednumberofpebblestodistributeacrossanNxNgameboard(Ndrawnfrom[3,15]),whereeachsquareontheboardcontainssomepositivepointvaluebetween10and99,inclusive.給定一個N*N個矩陣（3<=N<=15)，要你選擇若干個數(shù)，使得最后所選的數(shù)總和最大。選數(shù)的規(guī)則是如果選了某個數(shù)，那么它的八個相鄰方向的數(shù)都不能選。狀態(tài)？轉(zhuǎn)移？思考題：方格選數(shù)最大HDU2167

題目大意：例題六：優(yōu)盤質(zhì)量題意：n個完全相同的優(yōu)盤和h層高樓，希望知道優(yōu)盤最高在哪一層扔下來不會壞（定義為結(jié)實度），問最壞的情況下要扔幾次。比如2個優(yōu)盤4層樓，先從3樓扔， 如果沒壞，那么再在4樓扔 如果壞了，那么還剩1個優(yōu)盤，再在1樓扔 如果壞了，那么就是1層 如果沒壞，那么再在2樓扔所以這個方案最壞要扔3次。而且一定不會用到第3個優(yōu)盤。例題六：優(yōu)盤質(zhì)量題意：6.2優(yōu)盤質(zhì)量比較容易想到的是用f[i,j]表示現(xiàn)在有i層樓，j個優(yōu)盤，最好的方案最壞要扔多少次。狀態(tài)轉(zhuǎn)移方程可以這樣考慮：假定第一次在第x層試。如果壞了的話，下一步就是要確定在第1到第x-1層哪一層會壞或者都不會壞，而這一步還剩下j-1個優(yōu)盤，所以這一步最少要扔的次數(shù)就應(yīng)該是f[x-1,j-1]。如果沒壞的話，下一步就是要確定在第x+1到第i層哪一層會壞或者都不會壞，而這一步還剩下j個優(yōu)盤，所以這一步最少要扔的次數(shù)就應(yīng)該是f[i-x,j]。6.2優(yōu)盤質(zhì)量比較容易想到的是用f[i,j]表示現(xiàn)在有i層6.3優(yōu)盤質(zhì)量要考慮最壞的情況，所以第一次在第x層試的最壞要扔的次數(shù)就是max{f[x-1,j-1],f[i-x,j]}+1。所以f[i,j]=min{max{f[x-1,j-1],f[i-x,j]}+1|1<=x<=i}考慮到當(dāng)n很大時（大于log2h），就可以使用二分策略，最壞要扔的次數(shù)可以直接算出，所以n不會超過log2h。所以總的時間復(fù)雜度是O(h*h*log2h)。f[i,j]f[i-x,j]f[x-1,j-1]第x層6.3優(yōu)盤質(zhì)量要考慮最壞的情況，所以第一次在第x層試的最壞6.4優(yōu)盤質(zhì)量這個動態(tài)規(guī)劃算法雖然是正確的，但是有沒有更好的方法呢。換一個角度思考：如果有i個優(yōu)盤，規(guī)定最多扔j次，設(shè)最多能在