7.6 分组的背包问题7.7 有依赖的背包问题7.8 泛化物品

7.6 分组的背包问题

【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。这些物品被划分为 K 组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使价值总和最大。
1. 状态表示：设 f[k][c]为前 k 组物品花费 c 时可以获得的最大价值。
2. 状态转移方程：
注意循环的顺序。

 

for (int k=1;i<=K;i++)
for (int c=C;c>=0;c--)
for each (int i in 第k组) // 伪代码，指“for (所有属于组k的物品i)”
if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]);

在“金明的预算方案”（NOIP2006,2）中，就可以把主件、附件组合成一个分组背包（一组最多 4 个物体，最少 1 个物体）。

7.7 有依赖的背包问题

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

7.8 泛化物品

有这样一种物品，名字叫做泛化物品。有一个函数 h(x)，当分配给物品的费用为 a 时，能得到的价值就是h(a)。
实际上，前面总结的所有背包都可以看做泛化物品，只不过在某些时候 h 的值为 0。
如果面对两个泛化物品 h 和 l，要用给定的费用从这两个泛化物品中得到最大的价值，怎么求呢？事实上，对于一个给定的费用 v，只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的，对于 0～C 的每一个整数 c，可以求得费用 c 分配到 h 和 l 中的最大价值 f(v)：
f(v)＝max{h(k)＋l(c－k)}，0≤k≤c。
可以看到，f 也是一个由泛化物品 h 和 l 决定的定义域为 0～C 的函数，也就是说，f 是一个由泛化物品 h和 l 决定的泛化物品，f 是 h 与 l 的和。这个运算的时间复杂度取决于背包的容量，是 O(V
2)。
泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为 s，则答案就是 s[V]中的最大值。
一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。