點擊打開鏈接

第一種思路：

建立森林，dp[i][k]表示森林中在第i顆樹中選k個的最大價值 ， dp2[j]表示選j個的最大價值，對于每顆樹，都更新一次。

轉移方程：

dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k])；

dp2[j] = max(dp2[j],dp2[j-k]+dp[i][k])；

代碼：

#include <iostream>#include <cstring>#include <cstdio>#include <vector>using namespace std;const int maxn = 200+10;vector<int> G[maxn];int dp[maxn][maxn],dp2[maxn],a[maxn],va[maxn],n,m;void dfs(int u){	dp[u][1] = va[u];	dp[u][0] = 0;	for(int i=0; i<G[u].size(); i++){		int v = G[u][i];		dfs(v);		for(int j=m; j>=2; j--)			for(int k=0; k<j; k++) // 已經選了u  所以不能再兒子里選全部j個 k<j				dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);	}}int main(){	while(scanf("%d%d",&n,&m)!=EOF){		if(n==0 && m==0) break;		memset(dp,0,sizeof(dp));        memset(dp2,0,sizeof(dp2));        for(int i=0;i<maxn;i++)            G[i].clear();        memset(a,0,sizeof(a));		for(int i=1; i<=n; i++){			cin >> a[i] >> va[i];			if(a[i]!=0)				G[a[i]].push_back(i); // 形成森林		}		for(int i=1; i<=n; i++){			if(a[i] == 0)				dfs(i); // 每一顆樹都跑一遍01背包 dp[i][k]表示在第i顆樹中選k個的最大價值		}		for(int i=1; i<=n; i++){			if(a[i] == 0){				for(int j=m; j>=0; j--)					for(int k=0; k<=j; k++)						dp2[j] = max(dp2[j],dp2[j-k]+dp[i][k]); // dp2[j]表示選j個的最大價值，對于每顆樹，都更新一次			}		}		cout << dp2[m] << endl;	}}
第二種思路：
先把依賴關系建成樹，因為可能是森林，所以再建一個根節點把每個樹的根節點連起來就可以。然后樹上跑dfs，在回溯的過程中跑01背包。dp[u][i]表示在以u為根節點的子樹上，選i個物品的最大價值。然后轉移方程就是dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])，就是他可以從未更新的部分選j-k個，然后在已更新的那個兒子節點那里選k個，v是當前更新到的子節點，這樣把k從1到j-1掃一遍，就把這個子節點v對父節點u做的貢獻做出來了。然后這里說一下為什么j要從m到2更新，因為我們要用到dp[u][j-k]，而這個代表的是未更新當前結點的情況，所以如果j從小更新的話，dp[u][j-k]就是已更新這個子節點的情況了，然后就錯了，所以j要從大到小更新
#include <iostream>#include <cstring>#include <cstdio>#include <vector>using namespace std;const int maxn = 200+10;vector<int> G[maxn];int dp[maxn][maxn],a[maxn],va[maxn],n,m;void dfs(int u){	dp[u][1] = va[u];	dp[u][0] = 0;	for(int i=0; i<G[u].size(); i++){		int v = G[u][i];		dfs(v);		for(int j=m; j>=2; j--)			for(int k=0; k<j; k++)				dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]); 			// for(int k=1; k<=j; k++)			// 	dp[u][j] = max(dp[u][j],dp[u][k]+dp[v][j-k]); // u選k個 子節點中選j-k個	}}int main(){	while(scanf("%d%d",&n,&m),(n+m)){		memset(dp,0,sizeof(dp));        for(int i=0;i<maxn;i++)            G[i].clear();        memset(a,0,sizeof(a));        ++m; // 虛擬根節點0， 一定選		for(int i=1; i<=n; i++){			cin >> a[i] >> va[i];			G[a[i]].push_back(i);		}		dfs(0);		cout << dp[0][m] << endl;	}}