有界 0-1 多背包的任何伪多项式算法？

Any pseudo-polynomial algorithm for bounded 0-1 multi-knapsack?

提问人：TonySalimi 提问时间：4/14/2013 最后编辑：TonySalimi 更新时间：4/20/2013 访问量：918

问：

假设有 n 个项目，例如 i1、i2、....in，它们中的每一个都具有已知的有界权重 w1、w2、...wn.还有一套 m 背包，例如 k1、k2 和 km。背包是同质的，它们都具有相同的容量 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 和 ci。F 函数是一个线性函数，它获取其中项的属性并产生输出。

编辑3：本文似乎已经提出了解决多背包问题的精确解决方案。它可以用于我的情况吗？

算法 优化 编程 问题

评论

0赞 David Eisenstat 4/15/2013
由于对 F 没有约束，这个问题是从 APX 难问题中实现目标保持约简的一个很好的目标。
1赞 j_random_hacker 4/16/2013
您需要告诉我们有关评分功能的更多信息。就目前而言，它被允许是任意的——例如，它可以给项目 3、5 和 17 的组合打 100 分，而其他每个组合的分数为 0：如果不尝试适合的每个项目子集，就没有办法优化它。
0赞 j_random_hacker 4/16/2013
此外，为了证明它是NP硬的，你会减少垃圾箱包装，反之亦然。但是（目前假设有一个合理的评分函数）您不需要为此烦恼，因为通过设置 m=1 ：-P 将普通的背包简化为这个问题是微不足道的
0赞 TonySalimi 4/16/2013
@j_random_hacker：在编辑 2 中引入的功能 F。
1赞 blubb 4/16/2013
@hsalimi：你需要更具体。是否可以定义一个函数，该函数接受单个项目并返回其分数贡献，以便？GF(i1, ..., ik) = sum(G(i),i=1, i<k)

答：

1赞 גלעד ברקן 4/17/2013 #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)])])

上一个：C# 和 Java 语法是 LALR（x） 吗？

下一个：何时使用 =default 使析构函数默认？