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

12
votes

Suppose that there are n items, e.g i1, i2, .... in, each of them with a known bounded weight w1, w2, ... wn. There are also a set of m knapsacks e.g. k1, k2 and km. Knapsacks are homogeneous, that they all have the same capacity W. The function F can determine the score of each knapsack. The inputs of F are the items in each knapsack. So,

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

Now I want to put SOME items in the knapsacks in such a way that:

  1. The weight of items in a knapsack do not exceed its capacity W.
  2. The sum of scores for all knapsacks be maximum

Is there a polynomial time solution for this problem or not?

Note: The problem is 0-1, that is each item can be selected or not. All the problem parameters are bounded.

Edit 1: Isn't it possible to reduce this problem to bin packing and then conclude that it is an NP-hard problem?

Edit 2 In this problem, each item has three attributes, e.g. attributes ai, bi and ci. The F function is a linear function that gets the attributes of items inside it and produces the output.

Edit3: It seems that this paper has proposed a exact solution for the multi- knapsack problem. Can it be used in my case?

1
algorithmoptimizationconstraint-programmingknapsack-problem
With no constraints on F, this problem is a great target for objective-preserving reductions from APX-hard problems. – David Eisenstat
You need to tell us more about the scoring function. As it stands it is allowed to be arbitrary -- e.g. it could give the combination of items 3, 5 and 17 a score of 100 and every other combination 0: there's no way to optimise this without trying every subset of items that fit. – j_random_hacker
Also to prove it NP-hard you would reduce bin-packing to it, not vice versa. But (assuming for the moment a sensible scoring function) you don't need to bother with that since it's trivial to reduce ordinary knapsack to this problem by setting m=1 :-P – j_random_hacker
@j_random_hacker: In introduced Function F in Edit 2. – Gupta
@hsalimi: You need to be more specific. Is it possible to define a function G which takes a single item and returns its score contribution, such that F(i1, ..., ik) = sum(G(i),i=1, i<k)? – blubb

1 Answers

1
votes

How about this?

Given a standard dynamic solution in Haskell for a 0-1 knapsack problem, found 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

we add a stuffing mechanism, placing the inventory permutations sequentially in the next knapsack that has space,

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)

and substitute it for the mapped function. Putting it all together:

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 (total value followed by each knapsack's remaining weight capacity and contents):

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