樹(shù)型動(dòng)態(tài)規(guī)劃

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

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

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

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

5、問(wèn)題，那么我們還有沒(méi)有其他方法呢？12轉(zhuǎn)化為二叉樹(shù)如果該問(wèn)題僅僅只是一棵二叉樹(shù)，我們對(duì)兒子的分配就僅僅只需考慮左右孩子即可，問(wèn)題就變得很簡(jiǎn)單了。因此我們?cè)囍鴮⒃搯?wèn)題轉(zhuǎn)化為二叉樹(shù)求解。圖2就是對(duì)圖1采用孩子兄弟表示法所得到的二叉樹(shù)13動(dòng)態(tài)規(guī)劃仔細(xì)理解左右孩子的意義（如右圖）：左孩子：原根結(jié)點(diǎn)的孩子右孩子：原根結(jié)點(diǎn)的兄弟也就是說(shuō)，左孩子分配選課資源時(shí)，根結(jié)點(diǎn)必須要選修，而與右孩子無(wú)關(guān)。因此，我們?cè)O(shè)f(i,j)表示以i為根結(jié)點(diǎn)的二叉樹(shù)分配j門課程的所獲得的最大學(xué)分，則有，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個(gè)房間里這n個(gè)房間由n-1條走廊連接。每個(gè)房間里都有特別的保護(hù)魔法，在它的作用下，我無(wú)法通過(guò)這個(gè)房間，也無(wú)法取得其中的鑰匙。如果第i件房取消魔法需要耗費(fèi)cost能量,并取得keys數(shù)量的鑰匙 。如果我擁有的能量為P，從號(hào)房間出發(fā)，我最多能取得多少鑰匙？n=100，p,cost和keys都是整型。18分析樣例P=5可取,三間房的鑰匙，消耗為+,獲得的鑰匙為+19分析這n個(gè)房間由n-1條走廊連接，說(shuō)明該問(wèn)題的模型是一棵樹(shù)也就是說(shuō)，給出P的資源，如何在樹(shù)中分配這些資源，得到最大值，即鑰匙。這是典型的樹(shù)型動(dòng)態(tài)規(guī)劃問(wèn)題。將樹(shù)轉(zhuǎn)化為孩子兄弟表示法，由于根的左孩子還是它的孩子，右

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

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

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

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

12、劃設(shè)f(i,0)表示i結(jié)點(diǎn)被父親看到； f(i,1)表示i被它的兒子看到； f(i,2)表示在i安排警衛(wèi)；則狀態(tài)轉(zhuǎn)移方程為：時(shí)間復(fù)雜度O(N2)30procedure work(now:longint); var i,j,sum,tmp:longint; begin for i:=1 to tnow do work(wnow,i); /對(duì)每個(gè)兒子進(jìn)行處理 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 /枚舉哪個(gè)兒子放警衛(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é)樹(shù)型動(dòng)態(tài)規(guī)劃有一個(gè)共性，那就是它的基