【问题描述】依赖关系以图论中“森林”的形式给出,也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。 1. 第一种思想:将每个主件及其附件集合转化为物品组。不过,由于附件可能还有附件,就不能将每个附件都看作一个一般的01背包中的物品了。若这个附件也有附件集合,则它必定要被先转化为物品组,然后用分组的背包问题,解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。 2. 第二种思想:每个父结点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。 第三种思想:这已经触及到了“泛化物品”的思想,你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品,求某结点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
|