泛化物品

有这样一种物品，名字叫做泛化物品。有一个函数 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(V2)。

泛化物品的定义表明：在一个背包问题中，若将两个泛化物品代以它们的和，不影响问题的答案。事实上，对于其中的物品都是泛化物品的背包问题，求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和为 s，则答案就是 s[V]中的最大值。

一般而言，求解背包问题，即求解这个问题所对应的一个函数，即该问题的泛化物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。