2023年8月1日发(作者：)

有依赖的背包问题问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

⼀、算法

这⾥将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的⼀个附件集合组成。

按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）

考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所以⼀个主件和它的附件集合实际上对应于 分组的背包问题 中的⼀个物品组，每个选择了主件⼜选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法，因为物品组中的物品还是像原问题的策略⼀样多。

再考虑对每组中的物品应⽤⼀个简单有效的优化：对于⼀个物品组中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，我们可以对主件i的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0..V-c[i]所有这些值时相应的最⼤价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费⽤为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过⼀次01背包后，将主件i转化为 V-c[i]+1个物品的物品组，就可以直接应⽤ 分组的背包问题 的算法解决问题了。

更⼀般的问题

更⼀般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有⾃⼰的附件集合，限制只是每个物品最多只依赖于⼀个物品（只有⼀个主件）且不出现循环依赖。

解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。唯⼀不同的是，由于附件可能还有附件，就不能将每个附件都看作⼀个⼀般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后⽤分组的背包问题解出主件及其附件集合所对应的附件组中各个费⽤的附件所对应的价值。

事实上，这是⼀种树形DP，其特点是每个⽗节点都需要对它的各个⼉⼦的属性进⾏⼀次DP以求得⾃⼰的相关属性。这已经触及到了“泛化物品”的思想。这个“依赖关系树”每⼀个⼦树其实都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其所有⼉⼦的对应的泛化物品之和。

⼆、案例 代码：

2023年8月1日发(作者：)

有依赖的背包问题问题

这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表⽰若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，⼜被别的物品所依赖；另外，没有某件物品同时依赖多件物品。

⼀、算法

这⾥将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若⼲主件和依赖于每个主件的⼀个附件集合组成。

按照背包问题的⼀般思路，仅考虑⼀个主件和它的附件集合。可是，可⽤的策略⾮常多，包括：⼀个也不选，仅选择主件，选择主件后再选择⼀个附件，选择主件后再选择两个附件……⽆法⽤状态转移⽅程来表⽰如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）

考虑到所有这些策略都是互斥的（也就是说，你只能选择⼀种策略），所以⼀个主件和它的附件集合实际上对应于 分组的背包问题 中的⼀个物品组，每个选择了主件⼜选择了若⼲个附件的策略对应于这个物品组中的⼀个物品，其费⽤和价值都是这个策略中的物品的值的和。但仅仅是这⼀步转化并不能给出⼀个好的算法，因为物品组中的物品还是像原问题的策略⼀样多。

再考虑对每组中的物品应⽤⼀个简单有效的优化：对于⼀个物品组中的物品，所有费⽤相同的物品只留⼀个价值最⼤的，不影响结果。所以，我们可以对主件i的“附件集合”先进⾏⼀次01背包，得到费⽤依次为0..V-c[i]所有这些值时相应的最⼤价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品组，其中费⽤为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过⼀次01背包后，将主件i转化为 V-c[i]+1个物品的物品组，就可以直接应⽤ 分组的背包问题 的算法解决问题了。

更⼀般的问题

更⼀般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有⾃⼰的附件集合，限制只是每个物品最多只依赖于⼀个物品（只有⼀个主件）且不出现循环依赖。

解决这个问题仍然可以⽤将每个主件及其附件集合转化为物品组的⽅式。唯⼀不同的是，由于附件可能还有附件，就不能将每个附件都看作⼀个⼀般的01 背包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后⽤分组的背包问题解出主件及其附件集合所对应的附件组中各个费⽤的附件所对应的价值。

事实上，这是⼀种树形DP，其特点是每个⽗节点都需要对它的各个⼉⼦的属性进⾏⼀次DP以求得⾃⼰的相关属性。这已经触及到了“泛化物品”的思想。这个“依赖关系树”每⼀个⼦树其实都等价于⼀件泛化物品，求某节点为根的⼦树对应的泛化物品相当于求其所有⼉⼦的对应的泛化物品之和。

⼆、案例 代码：