選課樹形動(dòng)態(tài)規(guī)劃ppt課件.ppt

《選課樹形動(dòng)態(tài)規(guī)劃ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、選課給定M門課程，每門課程有一個(gè)學(xué)分要從M門課程中選擇N門課程，使得學(xué)分總和最大其中選擇課程必須滿足以下條件：每門課程最多只有一門直接先修課要選擇某門課程，必須先選修它的先修課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)

2、，必選根結(jié)點(diǎn)的條件。樣例分析如圖1，為兩棵樹，我們可以虛擬一個(gè)結(jié)點(diǎn)，將這些樹連接起來，那么森林就轉(zhuǎn)會(huì)為了1棵樹，選取結(jié)點(diǎn)時(shí)，從每個(gè)兒子出發(fā)進(jìn)行選取。顯然選M=4時(shí)，選3，2，7，6幾門課程最優(yōu)。動(dòng)態(tài)規(guī)劃如果我們單純從樹的角度考慮動(dòng)態(tài)規(guī)劃，設(shè)以i為根結(jié)點(diǎn)的樹選j門課程所得到的最大學(xué)分為f(i,j),設(shè)虛擬的樹根編號(hào)為0，學(xué)分設(shè)為0，那么，ans=f(0,n+1)如果樹根選擇1門功課，剩下j-1門功課變成了給他所有兒子如何分配的資源的問題，這顯然是背包問題。設(shè)前k個(gè)兒子選修了x門課程的最優(yōu)值為g(k,x)，則有其中:0<=

3、x<=j-1，ans=g(son(0),n+1)構(gòu)造樹結(jié)構(gòu)readln(n,m);inc(m);fori:=1tondo{父親表示法構(gòu)造樹}beginreadln(pr[i],v[i]);{pr是前驅(qū)結(jié)點(diǎn)，v價(jià)值}inc(t[pr[i]]);{t記錄結(jié)點(diǎn)的兒子個(gè)數(shù)}ne[pr[i],t[pr[i]]]:=i;{ne記錄樹}end;fori:=0tondo{ts記錄每個(gè)結(jié)點(diǎn)后代的個(gè)數(shù)}ts[i]:=ts[i-1]+t[i]+1;procedurework(now:longint);inline;vari,j,k,bas:

4、longint;beginfori:=1tot[now]dowork(ne[now,i]);bas:=ts[now-1]+1;fori:=bas+1tobas+t[now]do{f[i,j]表示i子樹內(nèi)選j的最大價(jià)值}forj:=1tomdobegin{g[i,j]是給每個(gè)節(jié)點(diǎn)分配的內(nèi)部背包的空間}g[i,j]:=g[i-1,j];{i不選}fork:=1tojdo{i選k門}ifg[i-1,j-k]+f[ne[now,i-bas],k]>g[i,j]thenbeging[i,j]:=g[i-1,j-k]+f[ne[n

5、ow,i-bas],k];fa[i,j]:=k;{記錄決策點(diǎn)}end;end;fori:=mdownto1do{計(jì)算f[i,j]}f[now,i]:=g[t[now]+bas,i-1]+v[now];end;進(jìn)一步分析上述狀態(tài)方程，需要枚舉每個(gè)結(jié)點(diǎn)的x個(gè)兒子，而且對(duì)每個(gè)兒子的選課選擇，需要再進(jìn)行遞歸處理。當(dāng)然這樣可以解決問題，那么我們還有沒有其他方法呢？轉(zhuǎn)化為二叉樹如果該問題僅僅只是一棵二叉樹，我們對(duì)兒子的分配就僅僅只需考慮左右孩子即可，問題就變得很簡(jiǎn)單了。因此我們?cè)囍鴮⒃搯栴}轉(zhuǎn)化為二叉樹求解。圖2就是對(duì)圖1采用孩子兄

6、弟表示法所得到的二叉樹動(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

7、,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,3)=max{f(1,1)+f(3,1)+1,f(1,2)+1}=9f(2,4)=max{f(1,3)+1,f(1,

8、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;