DAA — Рюкзак 0-1

В этом уроке ранее мы обсуждали проблему дробного ранца с использованием подхода Greedy. Мы показали, что подход Гриди дает оптимальное решение для дробного ранца. Тем не менее, эта глава рассмотрит проблему ранца 0-1 и ее анализ.

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

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

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

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

Пример-1

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

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

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

Пример-2

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

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

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

Для решения 0-1 ранца требуется подход динамического программирования.

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

Вор грабит магазин и может нести максимальный вес W в свой рюкзак. Есть n предметов, и вес i- ^го предмета равен w _i, а прибыль от выбора этого предмета равна p _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 >

Максимальный вес мамы 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 w i ≤ w then 
         if v i + c[i-1, w-w i ] then 
            c[i, w] = v i + c[i-1, w-w i ] 
         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, wW] .

Анализ

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