DAA - Рюкзак 0: 1

В этом руководстве ранее мы обсуждали задачу Fractional Knapsack с использованием жадного подхода. Мы показали, что жадный подход дает оптимальное решение для дробного рюкзака. Однако в этой главе будет рассмотрена задача о рюкзаке 0-1 и ее анализ.

В рюкзаке 0-1 предметы нельзя сломать, что означает, что вор должен забрать предмет целиком или оставить его. Это причина того, что он назван «рюкзаком 0-1».

Следовательно, в случае ранца 0-1 значение xi может быть 0 или же 1, где остальные ограничения остаются прежними.

0-1 Рюкзак не может быть решен с помощью жадного подхода. Жадный подход не гарантирует оптимального решения. Во многих случаях жадный подход может дать оптимальное решение.

Следующие примеры подтверждают наше утверждение.

Пример-1

Предположим, что вместимость ранца W = 25, а его предметы показаны в следующей таблице.

Вещь А B C D
Прибыль 24 18 18 10
Вес 24 10 10 7

Без учета прибыли на единицу веса (pi/wi), если мы применим жадный подход к решению этой проблемы, первый пункт Aбудет выбран , как это будет способствовать макс я мама прибыль среди всех элементов.

После выбора товара A, больше ни один элемент не будет выбран. Следовательно, для данного набора статей общая прибыль равна24. В то время как оптимальное решение может быть достигнуто путем выбора предметов,B и C, где общая прибыль составляет 18 + 18 = 36.

Пример-2

Вместо выбора элементов на основе общей выгоды, в этом примере элементы выбираются на основе отношения p i / w i . Предположим, что вместимость ранца W = 60, а его предметы показаны в следующей таблице.

Вещь А B C
Цена 100 280 120
Вес 10 40 20
Соотношение 10 7 6

Используя жадный подход, первый пункт Aвыбрано. Затем следующий элементBвыбран. Следовательно, общая прибыль составляет100 + 280 = 380. Однако оптимальное решение этого экземпляра может быть достигнуто путем выбора элементов,B и C, где общая прибыль 280 + 120 = 400.

Следовательно, можно сделать вывод, что жадный подход может не дать оптимального решения.

Чтобы решить 0-1 Рюкзак, требуется подход динамического программирования.

Постановка задачи

Вор ограбил магазин и может нести максимальный я ТЗ весаWв рюкзак. Естьn предметы и вес ith товар wi и прибыль от выбора этого элемента составляет pi. Какие предметы должен взять вор?

Подход динамического программирования

Позволять i быть элементом с наибольшим номером в оптимальном решении S за Wдолларов. потомS' = S - {i} оптимальное решение для W - wi долларов и ценность решения S является Vi плюс стоимость подзадачи.

Мы можем выразить этот факт в следующей формуле: определить c[i, w] быть решением для предметов 1,2, … , iи макс я вес мамыw.

Алгоритм принимает следующие входные данные

  • Макс я вес мамыW

  • Количество предметов n

  • Две последовательности v = <v1, v2, …, vn> и w = <w1, w2, …, wn>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

Набор предметов, которые нужно взять, можно вывести из таблицы, начиная с c[n, w] и проследить назад, откуда пришли оптимальные значения.

Если c [i, w] = c [i-1, w] , то элементi не является частью решения, и мы продолжаем трассировку с c[i-1, w]. В противном случае элементi является частью решения, и мы продолжаем трассировку с c[i-1, w-W].

Анализ

Этот алгоритм берет θ ( n , w ) раз, поскольку таблица c имеет ( n + 1). ( W + 1) записей, где для вычисления каждой записи требуется θ (1) времени.