【题目来源】
【题目描述】
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。如下图所示：
如果选择物品 5，则必须选择物品 1 和 2。这是因为 2 是 5 的父节点，1 是 2 的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
【输入格式】
第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。
接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 vi,wi,pi，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 pi=−1，表示根节点。 数据保证所有物品构成一棵树。
【输出格式】
输出一个整数，表示最大价值。
【输入样例】
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2
【输出样例】
11
【数据范围】
1≤N,V≤100，1≤vi,wi≤100。
父节点编号范围：内部结点 1≤pi≤N，根节点 pi=−1。
【算法分析】
● 有依赖的背包（树形背包）核心是物品间存在选子必选父的单向依赖关系，依赖结构通常为森林或多叉树，主流解法为树形 DP 结合分组背包自底向上合并；若题目中是双向强依赖、互相绑定的物品组（选其一必全选），则可先用并查集将连通块缩为超级物品，再套用普通 01 背包求解，两种思路对应不同依赖模型，共同构成完整解法体系。
● 有依赖的背包 / 树形背包 = 选儿子必须先选爹 + 把每个子树当成一组物品
● 邻接表：
● 核心代码解析
（1）f[u][i] 表示在以 u 为根的子树中（包含 u 本身），耗费体积不超过 i 时的最大价值。
（2）f[u][j] = max(f[u][j], f[t][k] + f[u][j - k]); 中，f[t][k] 表示给 u 的儿子 t 分不超过 k 体积所获最大价值，f[u][j−k] 表示给 u 自己 分剩下的不超过 j-k 体积所获最大价值。两者相加，就是所获总价值。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=105;
vector<int> g[N];
int vol[N],val[N];
int f[N][N];
int n,V,root;void dfs(int u) {for(int i=vol[u]; i<=V; i++) {f[u][i]=val[u]; //only yourself}for(int t:g[u]) {dfs(t); //deal with all the son/*Merge son's results onto father's record.j represents the total capacity to current subtree.k represents the capacity to child t.*/for(int j=V; j>=vol[u]; j--)for(int k=0; k<=j-vol[u]; k++)f[u][j]=max(f[u][j],f[t][k]+f[u][j-k]);}
}int main() {cin>>n>>V;for(int i=1; i<=n; i++) {int fa;cin>>vol[i]>>val[i]>>fa;if(fa==-1) root=i;else g[fa].push_back(i);}dfs(root);cout<<f[root][V]<<endl;return 0;
}/*
in:
5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2out:
11
*/
【参考文献】