有没有适用于有界0-1多重背包的伪多项式算法？

Question

假设有n个物品，例如i₁,i₂, .... i_n，它们每一个都有已知的有界重量w₁,w₂,...w_n。还有一组m个背包，例如k₁,k₂和k_m。这些背包是同质的，即它们都具有相同的容量W。函数F可以确定每个背包的分数。F的输入是每个背包中的物品。因此，

Score of each knapsack i = F(Items in knapsack i)

现在我想以某种方式将一些物品放入背包中，使得：

1. 每个背包中的物品重量不超过其容量W。
2. 所有背包内物品的分数总和最大。

这个问题是否有多项式时间解决方案？

注意：这个问题是0-1问题，即每个物品可以选择或不选择。所有问题参数都是有限制的。

编辑1：难道不能将此问题归约为装箱问题，从而得出它是NP难问题吗？

编辑2：在这个问题中，每个物品具有三个属性，例如属性a_i、b_i和c_i。F函数是一个线性函数，它获取其中物品的属性并产生输出。

编辑3：看起来 这篇论文已经提出了一个多背包问题的精确解法。它能用于我的情况吗？

- TonySalimi

---

没有对F施加任何限制，这个问题是从APX-hard问题进行目标保持约简的绝佳目标。 - David Eisenstat

你需要告诉我们更多关于得分函数的信息。按照目前的情况，它可以是任意的 - 例如，它可以给予物品3、5和17的组合100分，而其他每个组合都是0分：没有办法在不尝试每个适合的物品子集的情况下进行优化。 - j_random_hacker

另外，为了证明它是NP难问题，你需要将装箱问题归约到它，而不是相反。但是（假设有一个合理的评分函数），你不需要费心去做这件事，因为通过设置m = 1，将普通背包问题归约到这个问题是微不足道的 :-P - j_random_hacker

@hsalimi：您需要更具体一些。是否可以定义一个函数G，它接受单个项目并返回其得分贡献，使得F(i1, ..., ik) = sum(G(i),i=1, i<k)？ - blubb

@blubb：不，不能定义类似 G 的函数。 - TonySalimi

Answer 1

这个怎么样？

在这里找到了一个Haskell标准动态方案，用于解决0-1背包问题。

inv = [("map",9,150), ("compass",13,35), ("water",153,200), ("sandwich",50,160),
       ("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),
       ("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),
       ("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), 
       ("trousers",42,70), ("overclothes",43,75), ("notecase",22,80),
       ("sunglasses",7,20), ("towel",18,12), ("socks",4,50), ("book",30,10)]

knapsack = foldr addItem (repeat (0,[])) where
    addItem (name,w,v) list = left ++ zipWith max right newlist where
        newlist = map (\(val, names)->(val + v, name:names)) list
        (left,right) = splitAt w list

main = print $ (knapsack inv) !! 400

我们添加了一个填充机制，将库存排列顺序放置在下一个有空间的背包中。

stuff (name,w,v) left (v2,[]) = (v2,left)
stuff (name,w,v) left (v2,(cap, lst):xs) =
  if w <= cap 
     then (v + v2, left ++ [(cap - w, (name,w,v):lst)] ++ xs) 
     else stuff (name,w,v) (left ++ [(cap,lst)]) (v2,xs)

将其替换为映射函数。将所有内容放在一起：

inv = [("map",9,150), ("compass",13,35), ("water",153,200), ("sandwich",50,160),
       ("glucose",15,60), ("tin",68,45), ("banana",27,60), ("apple",39,40),
       ("cheese",23,30), ("beer",52,10), ("cream",11,70), ("camera",32,30),
       ("tshirt",24,15), ("trousers",48,10), ("umbrella",73,40), 
       ("trousers",42,70), ("overclothes",43,75), ("notecase",22,80),
       ("sunglasses",7,20), ("towel",18,12), ("socks",4,50), ("book",30,10)]

capacity = 200::Int
numKnapsacks = 3

stuff (name,w,v) left (v2,[]) = (v2,left)
stuff (name,w,v) left (v2,(cap, lst):xs) =
  if w <= cap 
     then (v + v2, left ++ [(cap - w, (name,w,v):lst)] ++ xs) 
     else stuff (name,w,v) (left ++ [(cap,lst)]) (v2,xs)

knapsack = foldr addItem (repeat (0, replicate numKnapsacks (capacity,[]))) 
  where addItem (name,w,v) list = left ++ zipWith max right newlist 
          where newlist = map (stuff (name,w,v) []) list
                (left,right) = splitAt w list

main = print $ (knapsack inv) !! 600

输出（总价值，后跟每个背包剩余的重量容量和内容）：

*Main> main
(1062,[(1,[("map",9,150),("tshirt",24,15),("trousers",42,70),
           ("overclothes",43,75),("notecase",22,80),("sunglasses",7,20),
           ("towel",18,12),("socks",4,50),("book",30,10)]),
       (0,[("compass",13,35),("cheese",23,30),("cream",11,70),
           ("camera",32,30),("trousers",48,10),("umbrella",73,40)]),
       (1,[("sandwich",50,160),("glucose",15,60),("tin",68,45),("banana",27,60),
           ("apple",39,40)])])

- גלעד ברקן