朱全民樹型動(dòng)態(tài)規(guī)劃.ppt

《朱全民樹型動(dòng)態(tài)規(guī)劃.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

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

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

3、一門直接先修課要選擇某門課程，必須先選修它的先修課M,N<=500分析每門課程最多只有1門直接先修課，如果我們把課程看成結(jié)點(diǎn)，也就是說每個(gè)結(jié)點(diǎn)最多只一個(gè)前驅(qū)結(jié)點(diǎn)。如果把前驅(qū)結(jié)點(diǎn)看成父結(jié)點(diǎn)，換句話說，每個(gè)結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)。顯然具有這種結(jié)構(gòu)的模型是樹結(jié)構(gòu)，要么是一棵樹，要么是一個(gè)森林。這樣，問題就轉(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)的條件。樣例分析如圖1，為兩棵樹，我們可以虛擬一個(gè)結(jié)點(diǎn)，將這些樹連接起來，那么森林就轉(zhuǎn)會(huì)為了1棵樹，選取結(jié)點(diǎn)時(shí)，從每個(gè)兒子出發(fā)進(jìn)行選取。顯然選M=4時(shí)，選

4、3，2，7，6幾門課程最優(yōu)。轉(zhuǎn)化為二叉樹如果該問題僅僅只是一棵二叉樹，我們對(duì)兒子的分配就僅僅只需考慮左右孩子即可，問題就變得很簡單了。因此我們?cè)囍鴮⒃搯栴}轉(zhuǎn)化為二叉樹求解。圖2就是對(duì)圖1采用孩子兄弟表示法所得到的二叉樹動(dòng)態(tài)規(guī)劃仔細(xì)理解左右孩子的意義（如右圖）：左孩子：原根結(jié)點(diǎn)的孩子右孩子：原根結(jié)點(diǎn)的兄弟也就是說，左孩子分配選課資源時(shí)，根結(jié)點(diǎn)必須要選修，而與右孩子無關(guān)。因此，我們?cè)O(shè)f(i,j)表示以i為根結(jié)點(diǎn)的二叉樹分配j門課程的所獲得的最大學(xué)分，則有，0<=k

5、f(5,1)=max{1,6}=6,f(7,1)=2f(4,1)=max{1,2}=2,f(1,1)=max{1,f(4,1)}=2f(3,1)=4,f(2,1)=max{1,4}=4f(5,2)=7f(7,2)=max{f(5,1)+2}=8f(4,2)=max{f(7,2),f(7,1)+1}=8f(1,2)=max{f(4,2),f(4,1)+2}=8f(2,2)=max{f(1,1)+1,f(3,1)+1)}=5f(7,3)=9f(4,3)=max{f(7,2)+1,f(7,3)}=9f(1,3)=max{f(4,2)+1,f(4,3)}=9f(2,

6、3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9f(2,4)=max{f(1,3)+1,f(1,2)+f(3,1)+1}=max{9+1,8+4+1}=13//讀入數(shù)據(jù),轉(zhuǎn)化為孩子兄弟表示fin>>n>>m;score[n+1]=0;brother[n+1]=0;//輸入數(shù)據(jù)并轉(zhuǎn)化為左兒子右兄弟表示法for(inti=1;i<=n;++i){inta,b;fin>>a>>b;if(a==0)a=n+1;score[i]=b;brother[i]=child[a];child[a]=i;}voiddfs(inti,intj){if(visi

7、ted[i][j])return;visited[i][j]=1;if(i==0

8、

9、j==0)return;dfs(brother[i],j);//如果不選i，則轉(zhuǎn)移到狀態(tài)(brother[i],j)f[i][j]=f[brother[i]][j];for(intk=0;kf[i][j])f[i]

10、[j]=f[brother[i]][k]+f[chi