动态规划之泛化物品的背包问题

2017年03月11日

1. 泛化物品的背包问题描述

一个物品或者物品组,没有固定的费用和价值,而是它的价值随着你分配给他的费用而变化。

更严格的定义是,在背包容量为V的背包问题中,泛化物品是一个定义域0…V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。

另一种理解是,一个泛化物品就是一个数组h[0…V],给它费用v,可得到价值h(v)。

考虑背包问题的不同情况,一个费用为c,价值为w的物品,如果它是01背包问题中的物品,那么把它看作泛化物品,它就是除了 以外,其他函数值都为0的一个函数;如果它是完全背包中的一个物品,那么把它看成这样的函数:仅当v被c整除时,有 ,其它函数值均为0;如果它是多重背包中的重复次数最多为m的物品,那么它对应的泛化函数有 ,仅当v被c整除,且 ,其它情况函数值均为0。

一个物品组可以看作一个泛化物品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的和。

泛化物品和运算的时间复杂度取决于背包的容量, 是
由泛化物品的定义可知:在一个背包问题中,若将两个泛化物品代替它们的和,不影响问题的答案。事实上,对于其中的物品都是泛化物品的背包问题,求它的答案的过程也就是求所有这些泛化物品之和的过程。若问题的和为s,则答案就是 中的最大值。

3. 背包问题中的泛化物品

一个背包问题中,可能会给出很多条件,包括每种物品的费用、价值等属性,物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。

也就是说,给定了所有条件以后,就可以对每个非负整数v求得:若背包容量为v,将物品装入背包可得到的最大价值是多少,这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品,或者说问题所对应的一个定义域为非负整数的函数:包含了关于问题本身的高度浓缩的信息。

一般而言,求得这个泛化物品的一个子定义域(例如0…V)的值之后,就可以根据这个函数的取值得到背包问题的最终答案。

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


参考

【1】背包九讲–泛化物品,http://love-oriented.com/pack/pack2alpha1.pdf


版权声明:本文为博主原创文章,转载请注明出处 本文总阅读量