DP笔记(11)：背包问题之依赖背包、树形背包(整理中，未完)
Author：zhoulujun Date：
本篇更偏向于竞赛题，但是现在面试越来越卷，有时间也还是啃一下，但是一时半会还没有搞懂，笔记整理中
有依赖的背包问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。
具体可以查看：https://www.luogu.com.cn/problem/P1064
思路分析
一般我们称呼不依赖于别的物品的物品为 主件，依赖于某主件的物品称为 附件
对于包含一个 主件 和若干个 附件 的结合由以下可能性：
仅选择主件
选择主件再选择一个附件
选择主件再选择若干个附件
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。
可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……
无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
对于有依赖的背包问题，一般采用树形DP来解决 ，对于某个子节点，需要依赖于其父节点
子物体体积集合划分
例题：
有 N 个物品和一个容量是 V的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。
如下图所示：
如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。
每件物品的编号是 i，体积是 vi，价值是 wi，依赖的父节点编号是 pi。物品的下标范围是 1…N。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
具体参看：https://blog.csdn.net/weixin_62224014/article/details/127413958
树上背包
这个推荐阅读 https://algo.itcharge.cn/10.Dynamic-Programming/06.Tree-DP/01.Tree-DP/
参考文章：
第七讲 有依赖的背包问题 https://www.kancloud.cn/kancloud/pack/70131
树上背包 - 有依赖的背包问题 https://writings.sh/post/knapsack-on-tree
转载本站文章《DP笔记(11)：背包问题之依赖背包、树形背包(整理中，未完)》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9125.html