DAA - Рюкзак 0: 1

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

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

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

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

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

Пример-1

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

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

Без учета прибыли на единицу веса (p_i/w_i), если мы применим жадный подход к решению этой проблемы, первый пункт 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 предметы и вес i^th товар w_i и прибыль от выбора этого элемента составляет p_i. Какие предметы должен взять вор?

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

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

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

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

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

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

• Две последовательности v = <v₁, v₂, …, v_n> и w = <w₁, w₂, …, w_n>

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) времени.