1. 泛化物品的背包问题描述
一个物品或者物品组,没有固定的费用和价值,而是它的价值随着你分配给他的费用而变化。
更严格的定义是,在背包容量为V的背包问题中,泛化物品是一个定义域0…V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。
另一种理解是,一个泛化物品就是一个数组h[0…V],给它费用v,可得到价值h(v)。
一个物品组可以看作一个泛化物品h,对于一个0…V中的v,若物品组中不存在费用为v的物品,则h(v) = 0,否则h(v)取所有费用为v的物品中的最大价值。在讨论的有依赖的背包问题中,每个“主件”及其“附件”的集合等价于一个物品组,可以看作成一个泛化物品。
2. 泛化物品的和
如果给定了两个泛化物品h和l,要用一定的费用,从这两个泛化物品中得到最大的价值,如何求解该问题?
对于一个给定的费用v,只需枚举将这费用如何分配给两个泛化物品即可。同样,对于0…V 的每一个整数v,可以求得费用v分配到h和l中的最大价值f(v),即
从公式可以看出,f是由泛化物品h和l决定的,定义域为0…V的函数,即,f是一个由泛化物品h和l决定的泛化物品。
将f定义为泛化物品h和l的和:h和l都是泛化物品,若函数f满足以上关系式,则称f是h和l的和。
3. 背包问题中的泛化物品
一个背包问题中,可能会给出很多条件,包括每种物品的费用、价值等属性,物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。
也就是说,给定了所有条件以后,就可以对每个非负整数v求得:若背包容量为v,将物品装入背包可得到的最大价值是多少,这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品,或者说问题所对应的一个定义域为非负整数的函数:包含了关于问题本身的高度浓缩的信息。
一般而言,求得这个泛化物品的一个子定义域(例如0…V)的值之后,就可以根据这个函数的取值得到背包问题的最终答案。
综上所述,一般而言,求解背包问题,即求解这个问题所对应的一个函数,即该问题的泛化物品。而求解某个泛化物品的一种常用方法就是将它表示 为若干泛化物品的和然后求之。
参考
【1】背包九讲–泛化物品,http://love-oriented.com/pack/pack2alpha1.pdf