树形背包也叫有依赖的背包，是一种背包问题的变体，与传统的背包问题不同的是，物品之间存在一定的层次结构，形成了一棵树。每个节点代表一个物品，节点之间通过边连接，表示层次关系。问题的目标是在遍历这棵树的过程中，选择一些物品放入背包，使得背包中物品的总价值最大。
在树形背包问题中，一个节点可以选择放入背包，也可以选择不放入背包。如果选择放入，就需要考虑该节点的子节点；如果选择不放入，可以考虑其他兄弟节点。问题的关键是如何在遍历树的过程中，动态规划地计算每个节点的状态。
这个树形结构选择才出现了有依赖，选这个物品，就要确保它的所有结点都被选择了，才能选择它，有点类似于数据结构中的拓扑序列，只有前面的都做完了才能选择做它，做它是有前提的，比如：学习数据结构是不是先要学习C/C++，C/C++是数据结构的先导课程。
这里用acwing上的例题：10. 有依赖的背包问题 - AcWing题库
话不多少直接上代码，注释在代码上。
#include<iostream> using namespace std; int N,V,p,root;//N个物品V背包容量 int v[105],w[105]; int a[105][105],b[105],f[105][105]; //a[i][j]表示以i为头结点有j个子节点，a[i][j]则存的是下标，b[i]表示以i为根结点有b[i]个子节点 //f[i][j]表示以i为根节点，背包容量为j所获得的最大价值 void dfs(int t){//有树就要考虑遍历用dfs深搜，t表示此时父节点 //此时t为父节点，要想选下面的，前提就是把父节点选了，所以初始背包容量大于v[t]都初始化w[t] for(int i=v[t];i<=V;i++){ f[t][i]=w[t]; } //下面不是一个父节点有许多子节点，按个遍历初始化它们，那么身为子节点又是父节点，又有子节点，递归下去 for(int i=0;i<b[t];i++){ int s=a[t][i]; dfs(s); for(int j=V;j>=v[t];j--){//类似01背包逆序遍历 for(int k=0;k<=j-v[t];k++){ f[t][j]=max(f[t][j],f[t][j-k]+f[s][k]);//状态转移方程 //f[t][j-k]+f[s][k]表示父节点要j-k的容量，子节点要k的容量 } } } } int main(){ cin>>N>>V; for(int i=1;i<=N;i++){ cin>>v[i]>>w[i]>>p; if(p==-1){//-1表示为根节点 root=i; }else{ a[p][b[p]++]=i;//可以看一下上面a[i][j]与b[i]的含义 } } dfs(root); cout<<f[root][V]<<endl; return 0; }
这里解释一下主要思想：要选一个物品，必须选它的父节点物品给他父结点保留v[t]的背包容量即可，剩下的V-v[t]给它的子节点，子节点又是父节点，它又有子节点，继续递归下去，max去寻找最大价值。
这篇博客特别鸣谢B站up主董晓老师，为我提供思路和一些资源，侵权必删，这里特别特别推荐去看一下董晓老师讲解的视频。看文章看不懂的可以看一下：E18 树形DP 树形背包_哔哩哔哩_bilibili
真的讲的特别好，细节方面说的也比文章中的多。本人水平有限一些地方写的不是很好，都是按照自己的思路写的，或许跟大家有所不同，鼓励大家提出疑问，探讨更好的思路解法，感谢大家支持。下篇更新求方案数问题。
