Подтвердить что ты не робот

Любой псевдополиномиальный алгоритм для ограниченного многострочного рюкзака 0-1?

Предположим, что существует n элементов, например я 1, я 2,.... я n, каждый из которых имеет известный ограниченный вес w 1, w 2,... w n. Существует также набор из m рюкзаков, например. k 1, k 2 и k m. Рюкзаки однородны, все они имеют одинаковую емкость W. Функция F может определять оценку каждого рюкзака. Входы F - это предметы в каждом рюкзаке. Таким образом,

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

Теперь я хочу поместить НЕКОТОРЫЕ элементы в рюкзаки таким образом, чтобы:

  • Вес предметов в рюкзаке не превышает его мощности W.
  • Сумма баллов для всех рюкзаков максимальная

Существует ли полиномиальное решение времени для этой проблемы или нет?

Примечание. Задача 0-1, то есть каждый элемент может быть выбран или нет. Все параметры проблемы ограничены.

Изменить 1: Нельзя ли уменьшить эту проблему до упаковки бинов, а затем сделать вывод, что это проблема NP-hard?

Изменить 2 В этой проблеме каждый элемент имеет три атрибута, например. атрибуты a i, b i и c i. Функция F - это линейная функция, которая получает атрибуты элементов внутри нее и выдает результат.

Edit3: Похоже, что этот документ предложил точное решение для проблемы с несколькими рюкзаками. Может ли он использоваться в моем случае?

4b9b3361

ОТВЕТЫ

Ответ 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


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