nbhkdz.com冰点文库

7背包问题九讲之有依赖的背包问题

时间:2012-05-14


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

算法
这个问题由 NOIP2006金明的预算方案一题扩展而来。遵从该题的提法, 将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为 “附件”。 由这个问题的简化条件可知所有的物品由若干主件和依赖于 每个主件的一个附件集合组成。

按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可 用的策略非常多,包括:一个也不选,仅选择主件,选择主件后再选择 一个附件, 选择主件后再选择两个附件……无法用状态转移方程来表示 如此多的策略。 (事实上, 设有 n 个附件, 则策略有2^n+1个, 为指数级。 )

考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略) , 所以一个主件和它的附件集合实际上对应于 P06中的一个物品组,每个 选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物 品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转 化并不能给出一个好的算法, 因为物品组中的物品还是像原问题的策略

一样多。

再考虑 P06中的一句话: 可以对每组中的物品应用 P02中“一个简单有

效的优化”。 这提示我们,对于一个物品组中的物品,所有费用相同
的物品只留一个价值最大的,不影响结果。所以,我们可以对主件 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个物品的物品组, 就可以直 接应用 P06的算法解决问题了。

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

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

事实上, 这是一种树形 DP, 其特点是每个父节点都需要对它的各个儿子 的属性进行一次 DP 以求得自己的相关属性。这已经触及到了“泛化物 品”的思想。看完 P08后,你会发现这个“依赖关系树”每一个子树都 等价于一件泛化物品, 求某节点为根的子树对应的泛化物品相当于求其 所有儿子的对应的泛化物品之和。

小结
NOIP2006的那道背包问题我做得很失败,写了上百行的代码,却一分未 得。 后来我通过思考发现通过引入“物品组”和“依赖”的概念可以加 深对这题的理解,还可以解决它的推广问题。用物品组的思想考虑那题 中极其特殊的依赖关系:物品不能既作主件又作附件,每个主件最多有 两个附件, 可以发现一个主件和它的两个附件等价于一个由四个物品组 成的物品组,这便揭示了问题的某种本质。

我想说:失败不是什么丢人的事情,从失败中全无收获才是。


赞助商链接

背包问题九讲

有依赖的背包问题七讲 有依赖的背包问题另一种给物品的选取加上限制的方法。 第八讲 泛化物品我自己关于背包问题的思考成果,有一点抽象。 第九讲 背包问题...

背包九讲完整版

分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附:USACO 中的背包问题 目录第一讲 01 背包问题这是最基本的背包问题,...

8背包问题九讲之泛化问题

在背包容量为 V 的背包问题中,泛化物品是一个定义 域为0..V 中的整数的...6背包问题九讲之分组的背... 7背包问题九讲之有依赖的... 9背包问题九讲之...

6背包问题九讲之分组的背包问题

6背包问题九讲之分组的背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要介绍...5背包问题九讲之二维费用... 7背包问题九讲之有依赖的... 8背包问题九讲之...

背包九讲完整版 + hdu 代码

分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附:USACO 中的背包问题代码目录 第一讲 01 背包问题 第二讲 完全背包...

背包问题九讲+v1(深入浅出理解动态规划)

七讲 有依赖的背包问题 另一种给物品的选取加上限制的方法。 第八讲 泛化物品 我自己关于背包问题的思考成果,有一点抽象。 第九讲 背包问题问法的变化 试图...

背包问题九讲和源程序(答案)

七讲 有依赖的背包问题 另一种给物品的选取加上限制的方法。 第八讲 泛化物品 我自己关于背包问题的思考成果,有一点抽象。 第九讲 背包问题问法的变化 试图...

绝对经典背包九讲完整版

分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附:USACO 中的背包问题 前言本篇文章是我(dd_engi)正在进行中的一个...

背包问题九讲_DOC版

第五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化物品 第九讲 背包问题问法的变化 附:USACO 中的背包问题 前言本篇...

背包问题九讲

背包九讲_打印版 24页 2财富值 背包问题九讲(很详细) 18页 5财富值 背包九...P07: 有依赖的背包问题简化的问题 这种背包问题的物品间存在某种"依赖"的关系....