题意
有 N 个物品和一个容量是 V 的背包。
物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
思路
有依赖的背包问题
状态表示：f[i][j] 表示 以 i为根的子树在体积为 j 的情况下 物品价值的最大值
状态计算： 枚举分配多少背包空间给 以节点 i为父节点的子节点
详解看注释
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' //#define int long long using namespace std; inline int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } inline int lowbit(int x) { return x & -x; } typedef long long LL; typedef pair<int, int>PII; const int N = 105; int n, m; vector<int>vec[N]; int v[N], w[N]; int f[N][N]; // f[i][j] 表示 以 i 为根的子树 体积为 j 时物品价值最大值 void dfs(int u) { for (int i = 0; i < vec[u].size(); ++i) { //枚举物品 int son = vec[u][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]); } } } // 将当前点 u 加入 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; //体积小于 根节点 v[u] 时 一定为0 } void solve() { cin >> n >> m; int root = 0; for (int i = 1; i <= n; ++i) {// 建树 int p; cin >> v[i] >> w[i] >> p; if (p == -1)root = i; else vec[p].push_back(i); } dfs(root); cout << f[root][m] << endl; } signed main() { //int t; cin >> t; //while(t--) solve(); return 0; }
