题目10. 有依赖的背包问题题目描述有N NN个物品和一个容量是V VV的背包。物品之间具有依赖关系且依赖关系组成一棵树的形状。如果选择一个物品则必须选择它的父节点。如下图所示如果选择物品5 55则必须选择物品1 11和2 22。这是因为2 22是5 55的父节点1 11是2 22的父节点。每件物品的编号是i ii体积是v i v_ivi​价值是w i w_iwi​依赖的父节点编号是p i p_ipi​。物品的下标范围是1 … N 1…N1…N。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。输入格式第一行有两个整数N NNV VV用空格隔开分别表示物品个数和背包容量。接下来有N NN行数据每行数据表示一个物品。第i ii行有三个整数v i , w i , p i v_i,w_i,p_ivi​,wi​,pi​用空格隔开分别表示物品的体积、价值和依赖的物品编号。如果p i − 1 p_i−1pi​−1表示根节点。 数据保证所有物品构成一棵树。输出格式输出一个整数表示最大价值。数据范围1 ≤ N , V ≤ 100 1≤N,V≤1001≤N,V≤1001 ≤ v i , w i ≤ 100 1≤v_i,w_i≤1001≤vi​,wi​≤100父节点编号范围内部结点1 ≤ p i ≤ N 1≤p_i≤N1≤pi​≤N;根节点p i − 1 p_i−1pi​−1;时空限制1s / 64MB输入样例5 7 2 3 -1 2 2 1 3 5 1 4 7 2 3 6 2输出样例11代码1(链式前向星)#includeiostream#includecstringusingnamespacestd;constintMaxN10010,MaxV10010;intN,V,v[MaxN],w[MaxN],h[MaxN],e[MaxN],ne[MaxN],idx,f[MaxN][MaxV];voidadd(inta,intb){e[idx]b;ne[idx]h[a];h[a]idx;}voiddfs(intu){for(intih[u];~i;ine[i]){intsone[i];dfs(e[i]);//分组背包for(intjV-v[u];j0;j--){for(intk0;kj;k){f[u][j]max(f[u][j],f[u][j-k]f[son][k]);}}}// 将物品u加进去for(intjV;jv[u];j--){f[u][j]f[u][j-v[u]]w[u];}for(intj0;jv[u];j){f[u][j]0;}}intmain(){cinNV;memset(h,-1,sizeofh);introot0;for(inti1;iN;i){intp;cinv[i]w[i]p;if(p-1){rooti;}else{add(p,i);}}dfs(root);coutf[root][V];return0;}代码2vector#includebits/stdc.husingnamespacestd;constintN10010;intn,V,v[N],w[N],f[N][N],root;vectorintg[N];voiddfs(intu){intleng[u].size();for(inti0;ilen;i){//物品组intsong[u][i];dfs(son);for(intjV-v[u];j0;j--){//体积for(intk0;kj;k){//决策f[u][j]max(f[u][j],f[u][j-k]f[son][k]);}}}//最后选上第u件物品for(intjV;jv[u];j--)f[u][j]f[u][j-v[u]]w[u];//清空没选上u的所有状态for(intj0;jv[u];j)f[u][j]0;}intmain(){cinnV;for(inti1;in;i){inta,b,c;cinabc;if(c-1)rooti;elseg[c].push_back(i);v[i]a,w[i]b;}dfs(root);coutf[root][V];return0;}结果