題意：n座城堡，每個裡面都有寶物，要求在你可以攻占m個城堡得到的最多的寶物，但是如果要攻破一個城堡，必須要攻破它依賴的那個城堡，例如，如果a依賴b，那麼如果想要攻破a就必須先攻破b。把每個城堡看作是物品，那麼這個物品的城堡數量是1，價值就是寶物了。
解題思路：根據題意知道這種關系會形成一顆多叉樹，根節點是0.從P=0開始，
1、遍歷所有P的孩子，遇到某個孩子還有孩子，就把該節點當作P，繼續1，直到遍歷完所有的節點，如果P的所有孩子都沒有孩子，那麼轉到2，存在有的孩子有孩子，轉到3；
2、對P的所有孩子進行01背包，假設P的價值是Vp，P共有n個孩子，然後對每個孩子進行01背包（因為對於每個城堡只能取一次），那麼可以得到城堡數量從0到n對應的最大價值（0對應的肯定是0了），用dp[i]表示，i代表城堡數量，dp[i]代表價值，接著從i=0開始，都加上P的價值Vp（因為所有的物品都依賴P），同時城堡的個數也加1；最後把得到的n+1個物品保存到P點，這樣，這些物品就相當於分組背包裡面的一組背包了，儲存在castle裡面，然後接著步驟1的遍歷；
3、這個就很簡單了，由於已經遍歷過P所有孩子了，所以，只需要再從頭開始遍歷一遍所有孩子，如果遍歷的孩子還有孩子，那麼就把它的所有孩子當作是分組背包處理，如果遍歷的孩子沒有孩子，那麼就當01背包處理，最後會得到一個城堡數量從0到m（也就是題目給的城堡數量的上限，以為不確定P的所有孩子的個數，所以就用最大的m）對應的最大價值，這個時候，如果P是0，那麼就輸出dp[m]就好了，如果不是，像2一樣，dp[i]代表的價值都加上P的價值，數量也加1，也儲存在castle裡面，繼續步驟1的遍歷；
具體代碼如下：
（提示：結構體s[i]代表城堡i的信息：num表示城堡的數量，value代表價值，key是自身的序號，depend代表i依賴的城堡編號；list castle[i]記錄依賴i的城堡的信息）
[cpp]
#include <cstdio>
#include <string.h>
#include <iostream>
#include <list>
using namespace std;
#define N 205
struct ss{
int num,value,key,depend;//物品的個數，價值，自身的序號，依賴的序號；
}s[N],one;
list <ss> castle[N];
int dp[N],m;
void fun(int n)
{
int num=0,i,j,k,minn;
list <ss>::iterator p,q;
p=castle[n].begin();
while(p!=castle[n].end())
{
if(castle[(*p).key].size()!=0)
fun((*p).key);
p++;
}
memset(dp,0,sizeof(dp));
p=castle[n].begin();
while(p!=castle[n].end())
{
if(castle[(*p).key].size()!=0)
{
for(i=m;i>=0;i--)
{
q=castle[(*p).key].begin();
while(q!=castle[(*p).key].end())
{
if(i-(*q).num>=0)
dp[i]=max(dp[i],dp[i-(*q).num]+(*q).value);
q++;
}
}
}
else
{
for(i=m;i>=(*p).num;i--)
dp[i]=max(dp[i],dp[i-(*p).num]+(*p).value);
}
p++;
}
castle[n].clear();
if(!n)
cout<<dp[m]<<endl;
else
{
one.depend=n;one.key=n;
for(i=m;;i--)
{
if(dp[i])
{
one.num=i+1;one.value=dp[i]+s[n].value;
castle[n].push_back(one);
}
else
{
one.num=1;one.value=s[n].value;
castle[n].push_back(one);
break;
}
}
}
}
int main()
{
int n;
while(cin>>n>>m)
{
if(!n&&!m)
return 0;
int i,j,k,x;
for(i=0;i<=n;i++)
castle[i].clear();
for(i=0;i<n;i++)
{
scanf("%d%d",&s[i+1].depend,&s[i+1].value);
s[i+1].num=1; s[i+1].key=i+1;
castle[s[i+1].depend].push_back(s[i+1]);
}
fun(0);
}
}
作者：jiang199235jiangJJ
