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

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


背包问题九讲

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

4背包问题九讲之混合三种背包问题

P04: 混合三种背包问题问题如果将 P01、 P02、 P03混合起来。 也就是说, 有的物品只可以取一次 (01 背包) ,有的物品可以取无限次(完全背包) ,有的物品可以...

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

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

5背包问题九讲之二维费用的背包问题

P05: 二维费用的背包问题问题二维费用的背包问题是指:对于每件物品,具有两种不...7背包问题九讲之有依赖的... 8背包问题九讲之泛化问题... 9背包问题九讲之...

背包问题和TSP问题算法报告

广义背包问题一、问题描述广义背包问题的描述如下: 给定载重量为 M 的背包和 ...node 0 1 2 3 0 1 2 3 5 3 2 5 3 7 2 9 12 7 9 12 i/Vj {...

案例4:背包问题

案例4:背包问题_理学_高等教育_教育专区。案例:背包问题有一个徒步旅行者, 已知...( 7.00)= 6.00=5(单)*0(决策)+f(3, 7.00) 第 3 阶段 f3( 4....

背包问题的进一步讨论

的解决都依赖于一个高 效的背包问题解法(在这些整数规划问题中,每当需要定界的时候我们都需要解 决一个背包问题,因此,一个高效的背包问题解法就显得非常有必要...

背包问题题目及含义

DD 牛的背包九讲 P01: 01 背包问题 题目 有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c,价值是 w。求解将哪些物 品装入背包可使这些物品...

背包问题系列算法详解

背包问题系列算法详解_计算机硬件及网络_IT/计算机_专业资料。背包问题系列算法详解 背包问题是一个关于最优解的经典问题。通常被讨论的最多的,最经典的背包问题是 ...

背包九讲

背包九讲 P01: 01背包问题 P02: 完全背包问题 P03: 多重背包问题 P04: 混合...有依赖的背包问题 P08: 泛化物品 P09: 背包问题问法的变化P01: 01背包问题 ...