有依赖的背包问题

sxqn 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;
}