依赖背包

出自《背包九讲》

问题

每个物品都有依赖关系,如果i依赖于j,那么要买i物品,必须先买j物品。

限制条件: 每个物品最多只能依赖一件物品;没有循环依赖。

称每个有依赖的为附件,没有依赖的为主件。

思想

先考虑简化版,即每个附件都没有附件。

那么对于每个主件所在的物品集合里,我们可以先跑一次01背包,得到每个费用可得到的最大价值。然后把每个$(cost, val), c_i \leq cost \leq V $ 看作一个新的物品。这样问题就转化成了分组背包。

再考虑普通版,即每个附件也可能存在附件。

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

事实上,这是一种树形动态规划,其特点是,在用动态规划求每个父节点的属性之前,需要对它的各个儿子的属性进行一次动态规划式的求值。

Thank you for your support!