AcWing 10：有依赖的背包问题

【题目来源】https://www.acwing.com/problem/content/10/【题目描述】有 N 个物品和一个容量是 V 的背包。物品之间具有依赖关系且依赖关系组成一棵树的形状。如果选择一个物品则必须选择它的父节点。如下图所示如果选择物品 5则必须选择物品 1 和 2。这是因为 2 是 5 的父节点1 是 2 的父节点。每件物品的编号是 i体积是 vi价值是 wi依赖的父节点编号是 pi。物品的下标范围是 1…N。求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。输出最大价值。【输入格式】第一行有两个整数 NV用空格隔开分别表示物品个数和背包容量。接下来有 N 行数据每行数据表示一个物品。第 i 行有三个整数 vi,wi,pi用空格隔开分别表示物品的体积、价值和依赖的物品编号。如果 pi−1表示根节点。 数据保证所有物品构成一棵树。【输出格式】输出一个整数表示最大价值。​​​​​​​【输入样例】5 72 3 -12 2 13 5 14 7 23 6 2​​​​​​​【输出样例】11【数据范围】1≤N,V≤1001≤vi,wi≤100。父节点编号范围内部结点 1≤pi≤N根节点 pi−1。【算法分析】● 有依赖的背包树形背包核心是物品间存在选子必选父的单向依赖关系依赖结构通常为森林或多叉树主流解法为树形 DP 结合分组背包自底向上合并若题目中是双向强依赖、互相绑定的物品组选其一必全选则可先用并查集将连通块缩为超级物品再套用普通 01 背包求解两种思路对应不同依赖模型共同构成完整解法体系。​​​​​​​● 有依赖的背包 / 树形背包 选儿子必须先选爹 把每个子树当成一组物品● 邻接表https://blog.csdn.net/hnjzsyjyj/article/details/155789364● 核心代码解析1f[u][i] 表示在以 u 为根的子树中包含 u 本身耗费体积不超过 i 时的最大价值。2f[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 N105; vectorint g[N]; int vol[N],val[N]; int f[N][N]; int n,V,root; void dfs(int u) { for(int ivol[u]; iV; i) { f[u][i]val[u]; //only yourself } for(int t:g[u]) { dfs(t); //deal with all the son /*Merge sons results onto fathers record. j represents the total capacity to current subtree. k represents the capacity to child t. */ for(int jV; jvol[u]; j--) for(int k0; kj-vol[u]; k) f[u][j]max(f[u][j],f[t][k]f[u][j-k]); } } int main() { cinnV; for(int i1; in; i) { int fa; cinvol[i]val[i]fa; if(fa-1) rooti; else g[fa].push_back(i); } dfs(root); coutf[root][V]endl; return 0; } /* in: 5 7 2 3 -1 2 2 1 3 5 1 4 7 2 3 6 2 out: 11 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/159616887https://blog.csdn.net/hnjzsyjyj/article/details/159650172https://blog.csdn.net/hnjzsyjyj/article/details/155789364