本文主要是介绍动态规划 —— 背包问题 P07 —— 有依赖背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【简化的问题】
这种背包问题的物品间存在某种“依赖”的关系，也就是说，i依赖于j，表示若选物品i，则必须选物品j。
为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖，另外，没有某件物品同时依赖多件物品。
【算法】
将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”，所有的物品由若干主件和依赖于每个主件的一个附件集合组成。
按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其体积和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
考虑P06： 可以对每组中的物品应用P02中“一个简单有效的优化”。
这提示我们，对于一个物品组中的物品，所有体积相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到体积依次为0..V-w[i]所有这些值时相应的最大价值f'[0..V-w[i]]。那么这个主件及它的附件集合相当于V-w[i]+1个物品的物品组，其中体积为w[i]+k的物品的价值为f'[k]+c[i]。
也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为V-w[i]+1个物品的物品组，就可以直接应用P06的算法解决问题了。
【较一般的问题】
更一般的问题是：依赖关系以图论中“森林”（即多叉树的集合）的形式给出，也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。
这已经触及到了“泛化物品”的思想，看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
这篇关于动态规划 —— 背包问题 P07 —— 有依赖背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
