樹形動態規劃

樹形動態規劃，是指當動態規劃的各階段形成一棵樹,樹形動態規劃基本上可以分為2個部分，一個是建樹，另一個就是動態規劃。

樹形動態規劃
樹形動態規劃，是指當動態規劃的各階段形成一棵樹，利用各階段之間的關係（動態轉移方程），從葉節點（邊界）開始逐步向上一層的節點（即父節點）進行動態規劃，直到動規到根節點，（即原問題），求的問題的最優解．
典型例題：沒有上司的晚會等
沒有上司的晚會
【問題描述】
有個公司要舉行一場晚會。為了讓到會的每個人不受他的直接上司約束而能玩得開心，公司領導決定：如果邀請了某個人，那么一定不會再邀請他的直接的上司，但該人的上司的上司，上司的上司的上司……都可以邀請。已知每個人最多有唯一的一個上司。
已知公司的每個人參加晚會都能為晚會增添一些氣氛，求一個邀請方案，使氣氛值的和最大。
【輸入：】
第1行一個整數N（1<=N<=6000）表示公司的人數。
接下來N行每行一個整數。第i行的書表示第i個人的氣氛值x（-128<=x<=127）。
接下來每行兩個整數L，K。表示第K個人是第L個人的上司。
輸入以0 0結束。
【輸出】：
一個數，最大的氣氛值和。
【樣例輸入】
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
【樣例輸出】
5
【分析】
如上例，上司與小兵之間的關係構成一棵樹。
5
| \
3 4
| \ | \
1 2 6 7
又是求最優解，並且每一個節點的取捨關乎到全局 因此，此題可用樹形動態規劃
我們可用f&#91;v&#93;[0]存儲不選編號為V的節點的最優解，f&#91;v&#93;[1]存儲選編號為V的節點的最優解
#include<iostream>
using namespace std;
int main(){
int n,qf[201],f[201][2],shs[201],XB[201][201],shu[201][201],x,s,maxc,j,k,a,b,l,i;//qf存儲每個人的氣氛值，shs存儲每個人的上司，xb存儲沒個人的下屬，shu存儲構成的樹
cin>>n;
for(i=0;i<=n;i++){xb&#91;i&#93;[0]=0;shs&#91;i&#93;=0;}
for(i=1;i<=n;i++)cin>>qf&#91;i&#93;;l=1;k=1;
while(l!=0 || k!=0){
cin>>l>>k;
shs&#91;l&#93;=k;
xb&#91;k&#93;[0]++;
xb&#91;k&#93;&#91;xb&#91;k&#93;[0]&#93;=l;
}
maxc=0;
for(i=1;i<=n;i++)
{
x=i;s=1;
while(shs&#91;x&#93;!=0){x=shs&#91;x&#93;;s=s+1;}
shu&#91;s&#93;[0]++;
shu&#91;s&#93;&#91;shu&#91;s&#93;[0]&#93;=i;
if (s>maxc)maxc=s;
}//建樹,maxc存儲最大層數
for(i=maxc;i>=1;i--)
for(j=1;j<=shu&#91;i&#93;[0];j++)
{
if(xb&#91;shu&#91;i&#93;&#91;j&#93;&#93;[0]==0){
f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[0]=0;f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[1]=qf&#91;shu&#91;i&#93;&#91;j&#93;&#93;;
}
else
{
f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[0]=0;f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[1]=qf&#91;shu&#91;i&#93;&#91;j&#93;&#93;;
for(k=1;k<=xb&#91;shu&#91;i&#93;&#91;j&#93;&#93;[0];k++){
a=f&#91;xb&#91;shu&#91;i&#93;&#91;j&#93;&#93;&#91;k&#93;&#93;[0];b=f&#91;xb&#91;shu&#91;i&#93;&#91;j&#93;&#93;&#91;k&#93;&#93;[1];
f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[1]+=a;
if(b>a)a=b;
f&#91;shu&#91;i&#93;&#91;j&#93;&#93;[0]+=a;
}//動態轉移方程
}
}s=0;
for(i=1;i<=shu[1][0];i++){
a=f&#91;shu[1]&#91;i&#93;&#93;[0];b=f&#91;shu[1]&#91;i&#93;&#93;[1];
if(a<b)a=b;
s=s+a;
}//從頂頭上司那裡擇優選擇
cout<<s<<endl;
system("pause");
return 0;
}
大家看到，樹形動態規劃基本上可以分為2個部分，一個是建樹，另一個就是動態規劃，一個好的數據結構，能使你編程非常容易，這也是樹形動態規劃的難點之一