有界0-1多揹包的任何僞多項式算法？

假設有n個項，例如：I ，我，....我_Ñ，它們中的每一個已知的有界權重w 1 ，瓦特，... w _n。還有一套m揹包，例如ķ，K 2 和k_米。揹包是同質的，它們都具有相同的容量W.函數F可以確定每個揹包的得分。 F的輸入是每個揹包中的項目。所以，有界0-1多揹包的任何僞多項式算法？

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

現在我想放在揹包有些項目以這樣一種方式：

物品放進揹包的重量不超過其容量W.
總和的所有揹包的分數是最大的

是否存在這個問題的多項式時間解決方案？

注：問題是0-1，即每個項目可以被選擇或不。所有的問題參數都是有界的。

編輯1：是不是可以減少這個問題裝箱，然後得出結論，這是一個NP難的問題？

編輯2在這個問題中，每個項目有三個屬性，例如屬性一個_我，B _我和c _我。 F函數是一個線性函數，它獲取其中的項目屬性並生成輸出。

編輯3：看來this paper已經提出了一個多揹包問題的精確解。它可以用於我的情況嗎？

來源

2013-04-14 hsalimi

隨着F無約束，這個問題是客觀保留一個偉大的目標減少APX難題。 –

您需要告訴我們更多關於評分功能的信息。就其本身而言，它可以是任意的 - 例如它可以使項目3,5和17的組合得分爲100，並且每個其他組合0：如果不嘗試每個適合的項目子集，就無法優化這個項目。 –

另外爲了證明它NP是難的，你會減少垃圾箱* *，反之亦然。但是（假設現在是一個明智的評分函數），你不必爲此煩惱，因爲通過設置m = 1來減少*普通揹包*對於這個問題是微不足道的：-P –

這個怎麼樣？

鑑於哈斯克爾一個標準的動態解決方案爲0-1揹包問題，發現here，

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

OUTPUT（總價值，然後每個揹包的剩餘重量容量和內容）：

*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)])])

來源

2013-04-16 17:10:58

有界0-1多揹包的任何僞多項式算法？

回答

相關問題