樹型動態(tài)規(guī)劃

1、樹型動態(tài)規(guī)劃1加分二叉樹給定一個中序遍歷為1,2,3,n的二叉樹每個結(jié)點有一個權(quán)值定義二叉樹的加分規(guī)則為：左子樹的加分 右子樹的加分根的分數(shù)若某個樹缺少左子樹或右子樹，規(guī)定缺少的子樹加分為1。構(gòu)造符合條件的二叉樹該樹加分最大輸出其前序遍歷序列2樣例中序遍歷為1,2,3,4,5的二叉樹有很多，下圖是其中的三棵，其中第三棵加分最大，為145.3分析性質(zhì)：中序遍歷是按“左-根-右”方式進行遍歷二叉樹，因此二叉樹左孩子遍歷序列一定在根結(jié)點的左邊，右孩子遍歷序列一定在根結(jié)點的右邊！因此，假設(shè)二叉樹的根結(jié)點為k，那么中序遍歷為1,2,n的遍歷序列，左孩子序列為1,2,k-1，右孩子序列為k+1,k+2,n

2、，如下圖4動態(tài)規(guī)劃設(shè)f(i,j)中序遍歷為i,i+1,j的二叉樹的最大加分，則有： f(i,j)=maxfi,k-1*fk+1,j +dk顯然 f(i,i)=di答案為f(1,n)1=i=k=j=n時間復雜度 O(n3)要構(gòu)造這個樹，只需記錄每次的決策值，令b(i,j)=k，表示中序遍歷為i,i+1,j的二叉樹的取最優(yōu)決策時的根結(jié)點為k最后前序遍歷這個樹即可。5選課給定M門課程，每門課程有一個學分要從M門課程中選擇N門課程，使得學分總和最大其中選擇課程必須滿足以下條件：每門課程最多只有一門直接先修課要選擇某門課程，必須先選修它的先修課M,N=5006分析每門課程最多只有1門直接先修課，如果我們

3、把課程看成結(jié)點，也就是說每個結(jié)點最多只一個前驅(qū)結(jié)點。如果把前驅(qū)結(jié)點看成父結(jié)點，換句話說，每個結(jié)點只有一個父結(jié)點。顯然具有這種結(jié)構(gòu)的模型是樹結(jié)構(gòu)，要么是一棵樹，要么是一個森林。這樣，問題就轉(zhuǎn)化為在一個M個結(jié)點的森林中選取N個結(jié)點，使得所選結(jié)點的權(quán)值之和最大。同時滿足每次選取時，若選兒子結(jié)點，必選根結(jié)點的條件。7樣例分析如圖1，為兩棵樹，我們可以虛擬一個結(jié)點，將這些樹連接起來，那么森林就轉(zhuǎn)會為了1棵樹，選取結(jié)點時，從每個兒子出發(fā)進行選取。顯然選M=4時，選3，2，7，6幾門課程最優(yōu)。8動態(tài)規(guī)劃如果我們單純從樹的角度考慮動態(tài)規(guī)劃，設(shè)以i為根結(jié)點的樹選j門課程所得到的最大學分為f(i,j), 設(shè)虛擬的

4、樹根編號為0，學分設(shè)為0，那么，ans=f(0,n+1)如果樹根選擇1門功課，剩下j-1門功課變成了給他所有兒子如何分配的資源的問題，這顯然是背包問題。設(shè)前k個兒子選修了x門課程的最優(yōu)值為g(k,x)，則有其中: 0=xgi,j then begin gi,j:=gi-1,j-k+fnenow,i-bas,k; fai,j:=k;記錄決策點 end; end; for i:=m downto 1 do計算fi,j fnow,i:=gtnow+bas,i-1+vnow; end;11進一步分析上述狀態(tài)方程，需要枚舉每個結(jié)點的x個兒子，而且對每個兒子的選課選擇，需要再進行遞歸處理。當然這樣可以解決

5、問題，那么我們還有沒有其他方法呢？12轉(zhuǎn)化為二叉樹如果該問題僅僅只是一棵二叉樹，我們對兒子的分配就僅僅只需考慮左右孩子即可，問題就變得很簡單了。因此我們試著將該問題轉(zhuǎn)化為二叉樹求解。圖2就是對圖1采用孩子兄弟表示法所得到的二叉樹13動態(tài)規(guī)劃仔細理解左右孩子的意義（如右圖）：左孩子：原根結(jié)點的孩子右孩子：原根結(jié)點的兄弟也就是說，左孩子分配選課資源時，根結(jié)點必須要選修，而與右孩子無關(guān)。因此，我們設(shè)f(i,j)表示以i為根結(jié)點的二叉樹分配j門課程的所獲得的最大學分，則有，0=kj n m; scoren+1 = 0; brothern+1 = 0; / 輸入數(shù)據(jù)并轉(zhuǎn)化為左兒子右兄弟表示法 for (

6、int i=1; i a b; if (a = 0) a = n + 1; scorei = b; brotheri = childa; childa = i; 16void dfs( int i, int j) if (visitedij) return; visitedij = 1; if (i=0 | j=0) return; dfs(brotheri, j); / 如果不選i，則轉(zhuǎn)移到狀態(tài)(brotheri, j) fij = fbrotherij; for (int k=0; k fij) fij = fbrotherik + fchildij-k-1 + scorei; 17通向自

7、由的鑰匙通向自由的鑰匙被放n個房間里這n個房間由n-1條走廊連接。每個房間里都有特別的保護魔法，在它的作用下，我無法通過這個房間，也無法取得其中的鑰匙。如果第i件房取消魔法需要耗費cost能量,并取得keys數(shù)量的鑰匙 。如果我擁有的能量為P，從號房間出發(fā)，我最多能取得多少鑰匙？n=100，p,cost和keys都是整型。18分析樣例P=5可取,三間房的鑰匙，消耗為+,獲得的鑰匙為+19分析這n個房間由n-1條走廊連接，說明該問題的模型是一棵樹也就是說，給出P的資源，如何在樹中分配這些資源，得到最大值，即鑰匙。這是典型的樹型動態(tài)規(guī)劃問題。將樹轉(zhuǎn)化為孩子兄弟表示法，由于根的左孩子還是它的孩子，右

8、孩子是它的兄弟，因此：樹根獲取資源，則左右孩子均可獲取資源樹根不獲取資源，則左孩子不能獲取資源，右孩子可獲取資源。20動態(tài)規(guī)劃設(shè)f(i,j)表示以i為根結(jié)點的二叉樹分配分配j的能量所獲得的最多鑰匙數(shù)，則有，初始：f(i,0)=0答案： f (1,P)時間復雜度為O(NP2)21軟件安裝（2010河南省選）有N個軟件，對于一個軟件i，它要占用Wi的磁盤空間，它的價值為Vi。我們希望從中選擇一些軟件安裝到一臺磁盤容量為M計算機上，使得這些軟件的價值盡可能大（即Vi的和最大）。軟件之間存在依賴關(guān)系，即軟件i只有在安裝了軟件j（包括軟件j的直接或間接依賴）的情況下才能正確工作（軟件i依賴軟件j)。幸運

9、的是，一個軟件最多依賴另外一個軟件。如果一個軟件不能正常工作，那么它能夠發(fā)揮的作用為0。我們現(xiàn)在知道了軟件之間的依賴關(guān)系：軟件i依賴軟件Di。 一個軟件只能被安裝一次，如果一個軟件沒有依賴則Di=0，這時只要這個軟件安裝了，它就能正常工作?，F(xiàn)在請你設(shè)計出一種方案，安裝價值盡量大的軟件。22分析由于軟件存在先后約束關(guān)系，因此簡單按軟件先后順序進行動態(tài)規(guī)劃，會不符合無后效應(yīng)原理，因此我們需要在進行動態(tài)規(guī)劃前進行預處理。若安裝軟件i必須先安裝j,則從i向j連一條有向弧，則軟件的約束關(guān)系就構(gòu)成了一個有向圖。如下圖：可以看出如果有k個制約關(guān)系，則有k條邊，中間會存在環(huán)23分析處理環(huán)：由于環(huán)為互為前提，要

10、選擇環(huán)中的一個必須都進行選擇，因此可以將環(huán)縮成一個點，這個點為權(quán)值和價值為其他點的和。孤立點沒有與其他點也沒有任何關(guān)系，可以不管。如果把每個連通分量看成一棵樹，則圖變成了為一個森林，圖2。24樹型動態(tài)規(guī)劃顯然這個森林可以采用樹型動態(tài)規(guī)劃，先將它兒叉樹。設(shè)f(i,j)表示以i為根結(jié)點的二叉樹分配j資源的最大價值25警衛(wèi)安排一個有N個區(qū)域的樹結(jié)構(gòu)上需要安排若干個警衛(wèi)；每個區(qū)域安排警衛(wèi)所需要的費用是不同的；每個區(qū)域的警衛(wèi)都可以望見其相鄰的區(qū)域，只要一個區(qū)域被一個警衛(wèi)望見或者是安排有警衛(wèi)，這個區(qū)域就是安全的；任務(wù)：在確保所有區(qū)域都是安全的情況下，找到安排警衛(wèi)的最小費用；0n=720；26分析樣例該圖有

11、6個區(qū)域如圖1，安排情況如圖2，紅色點為安排了警衛(wèi)。2號警衛(wèi)可以觀察1，2，5，6；3號警衛(wèi)可以觀察1，3； 4號警衛(wèi)可以觀察1，4；費用：16+5+4=2527分析對于每個點i，都有3種狀態(tài)分別為：要么在父親結(jié)點安排警衛(wèi)，即被父親看到要么在兒子結(jié)點安排警衛(wèi)，即被兒子看到要么安排警衛(wèi)對于ii被父親看到，這時i沒有安排警衛(wèi)，i的兒子要么安排警衛(wèi)，要么被它的后代看到。i被兒子看到，即i的某個兒子安排了警衛(wèi)，其他兒子需要安排警衛(wèi)或者被它的后代看到。i安排了警衛(wèi)，i的兒子可能還需要安排警衛(wèi)，這樣可能有更便易的方式照顧到它的后代；所以i的兒子結(jié)點被i看到，可能安排警衛(wèi)，可能被它的后代看到。2829動態(tài)規(guī)

12、劃設(shè)f(i,0)表示i結(jié)點被父親看到； f(i,1)表示i被它的兒子看到； f(i,2)表示在i安排警衛(wèi)；則狀態(tài)轉(zhuǎn)移方程為：時間復雜度O(N2)30procedure work(now:longint); var i,j,sum,tmp:longint; begin for i:=1 to tnow do work(wnow,i); /對每個兒子進行處理 fnow,0:=0; /以下處理now被父親看到 for i:=1 to tnow do inc(fnow,0,fwnow,i,1); /now的兒子被兒子看到sum:=0;/以下處理在now被兒子看到的 for i:=1 to tnow d

13、o / now的兒子被兒子看到或者或安排警衛(wèi)； inc(sum, min(fwnow,i,1,fwnow,i,2); fnow,1:=maxlongint; for i:=1 to tnow do /枚舉哪個兒子放警衛(wèi) begin tmp:=sum-min(fwnow,i,1,fwnow,i,2)+fwnow,i,2; fnow,1:=min(fnow,1,tmp); end; fnow,2:=cnow; /以下處理在now放置警衛(wèi) for i:=1 to tnow do Inc(fnow,2, min(min(fwnow,i,0,fwnow,i,1),fwnow,i,2); fnow,1:=min(fnow,1,fnow,2) ;1包含了2狀態(tài)，取優(yōu)值 end;31總結(jié)樹型動態(tài)規(guī)劃有一個共性，那就是它的基