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

[toc]

说明:

本文所讲内容摘录自崔添翼:背包九讲,并对其中的数学内容和一些较为复杂的内容进行了删减,增加了基础的例题,只是面向初学者或者不需要深入理解背包及其衍生问题的读者,如果有能力并且有意愿加深理解,本文可能会对您形成误导,请移步崔添翼:背包九讲.

有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

例如选择物品5的时候,物品1和物品2也要选择.

      1
    /   \
   2	   3
 /  \
4	   5

题目解法

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

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

完全背包问题有一个很简单有效的优化，是这样的：若两件物品 $i$、$j$ 满足 $C_i ≤ C_j$ 且 $W_i ≥ W_j$，则将可以将物品 $j$ 直接去掉，不用考虑。我们可以想到，对于第 k 个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，可以对主件 k 的“附件集合” 先进行一次 01 背包 ，得到费用依次为 $0. . .V − C_k$ 所有这些值时相应的最大价值 $F_k[0 . . . V − C_k]$。那么，这个主件及它的附件集合相当于 $V − C_k + 1$ 个物品的 物品组，其中费用为 $v$ 的物品的价值为 $F_k[v −C_k] +W_k$，$v$ 的取值范围是 $C_k ≤ v ≤ V$。 也就是说，原来指数级的策略中，有很多策略都是冗余的，通过一次 01 背包后，将主件 $k$ 及其附件转化为 $V −C_k + 1$ 个物品的物品组，就可以直接应用 分组背包 的算法解决问题了。

相关题目练习

题目URL

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

      1
    /   \
   2	   3
 /  \
4	   5

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i，体积是 $v_i$，价值是 $w_i$，依赖的父节点编号是 $p_i$。物品的下标范围是 $1…N$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N，V，用空格隔开，分别表示物品个数和背包容量。

接下来有 N 行数据，每行数据表示一个物品。
第 i 行有三个整数 $v_i,w_i,p_i$，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。
如果 $p_i=−1$，表示根节点。 数据保证所有物品构成一棵树。

输出格式

输出一个整数，表示最大价值。

数据范围

$1≤N,V≤1001≤N,V≤100$
$1≤v_i,w_i≤1001≤v_i,w_i≤100$

父节点编号范围：

• 内部结点：$1≤p_i≤N \space\space 1≤p+i≤N;$
• 根节点 $p_i=−1;$

输入样例

5 7
2 3 -1
2 2 1
3 5 1
4 7 2
3 6 2

输出样例：

11

赏

谢谢你请我吃糖果

微信