动态规划之有依赖的背包问题

2017年03月10日

1. 简化的有依赖的背包问题描述

背包问题的物品间存在某种“依赖”关系,即物品i依赖于物品j,若要选择物品i,则必须选择物品j。简化起见,先设没有某个物品即依赖于别的物品,又被别的物品所依赖;另外,没有某个物品同时依赖于多个物品。

2. 有依赖的背包问题算法

将不依赖别的物品的物品称为“主件”,将依赖于某主件的物品称之为“附件”,根据简化条件,该问题即可以描述为:所有的物品,由若干主件和依赖于每个主件的一个附件集合组成。

考虑到选择某个“主件”,或选择“主件+附件”的组合,这些策略是互斥的,只能选择一种策略。

所以,一个“主件”和它的附件集合,实际上是一个物品组,每一个选择某个“主件”或者“主件+附件”的策略,实际上相当于这个物品组中的一个物品,其费用和价值,都是策略中的物品的值的总和。这样的话,对于该简化描述的依赖背包问题的,可以转化为分组背包问题,参考分组背包问题的解决思路,可以解决该问题。

考虑到一个“主件”和它的附件集合,存在多种组合策略,需要考虑对每组内的物品进行组合优化。对于第k个物品组中的物品,所有费用相同的物品,只留一个价值最大的,不影响结果。因此,可以对主件k的“附件”集合进行一次01背包,得到的费用依次为 ,所有这些值对应的最大价值,那么该主件及其附件集合相当于个物品的物品组,其中费用为v的物品的价值为,v的取值范围是
通过对一个“主件”和它的附件集合使用一次01背包方法,可以将指数级的策略,转化为个物品的物品组,之后可以将其用于分组的背包问题,予以解决。

3. 较一般的问题

更一般的问题是:依赖关系以图论中的“森林”形式给出,即主件的附件,仍然可以有自己的附件集合。限制只是每个物品最多只依赖一个物品(只有一个主件),且不出现循环依赖。

事实上,这是一种树形动态规划,其特点是,在用动态规划求每个父节点 的属性之前,需要对它的各个儿子的属性进行一次动态规划式的求值。这已经 触及到了“泛化物品”的思想。

将在学习完“泛化物品”的思想之后,对该部分问题的解决思路进行详细描述。(你会发现这个“依赖关系树”每一个 子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其 所有儿子的对应的泛化物品之和。)


参考

【1】背包九讲–有依赖的背包问题,http://love-oriented.com/pack/pack2alpha1.pdf


版权声明:本文为博主原创文章,转载请注明出处 本文总阅读量