题目传送门
我们可以把依赖关系用一棵树来表示，我们选了一个节点就节点的父亲都要选。
然后我们可以把有依赖的背包问题看成是分组背包问题，每一个结点是看成是分组背包问题中的一个组，子节点的每一种选择我们都看作是组内的一种物品，因此我们可以通过分组背包的思想去写。
但我们如何去遍历子节点的每一种选择，即组内的物品，我们的做法是从叶子结点开始往根节点做，并使用数组表示的邻接表来存贮每个结点的父子关系。
#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; }