有依賴的背包問題

• 2020 年 11 月 14 日
• 筆記

題目傳送門

思路

我們可以把依賴關係用一棵樹來表示，我們選了一個節點就節點的父親都要選。

然後我們可以把有依賴的背包問題看成是分組背包問題，每一個結點是看成是分組背包問題中的一個組，子節點的每一種選擇我們都看作是組內的一種物品，因此我們可以通過分組背包的思想去寫。

但我們如何去遍歷子節點的每一種選擇，即組內的物品，我們的做法是從葉子結點開始往根節點做，並使用數組表示的鄰接表來存貯每個結點的父子關係。

#include <bits/stdc++.h>
using namespace std;
int n,m,root,head[105],nxt[105],ver[105],cnt,v[105],w[105],f[105][105];

void add_edge(int u,int v) { ver[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt; }

void dfs(int u) {
	for(int i=head[u];i;i=nxt[i]) {
		int son=ver[i];
		dfs(son);
		for(int j=m-v[u];j>=0;j--) {
			for(int k=0;k<=j;k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
		}
	}
	for(int i=m;i>=v[u];i--) f[u][i]=f[u][i-v[u]]+w[u];
	for(int i=0;i<v[u];i++) f[u][i]=0;
	return ;
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i=1,x;i<=n;i++) {
		scanf("%d %d %d",&v[i],&w[i],&x);
		if(x==-1) root=i;
		else add_edge(x,i);
	}
	dfs(root);
	printf("%d",f[root][m]);
	return 0;
}