0/1 Knapsack & Динамічне Програмування

Проблема пакування без обходів

У вас є рюкзак із місткістю W та n предметів, кожен з яких має вагу та значення. Ви можете взяти кожен елемент повністю або взагалі – немає поділу елемента навпіл, тому і ‘0/1’. Мета полягає у виборі підмножини елементів, яка максимізує загальне значення, зберігаючи при цьому загальну вагу на рівні або нижче W. З n елементами існує 2^n можливих підмножин, і перевірка всіх з них є можливою лише для малих n. Динамічне програмування перетворює цей експоненційний пошук у щось значно дешевше, помітивши, що проблема має перекриваючіся підпроблеми.

Рекурентне співвідношення: take-vs-skip

Визначте dp[i][w] як найкращу ціну, яку можна отримати, використовуючи лише перші i предметів з бюджетом ваги w. Для кожного предмета i є два варіанти, і dp[i][w] дорівнює кращому з них:

dp[0][w] = 0 для всіх w (немає предметів) dp[i][w] = dp[i-1][w] якщо weight[i] > w (потрібно пропустити — занадто важко) dp[i][w] = max( dp[i-1][w], // пропустіть предмет i dp[i-1][w - weight[i]] + value[i] ) // візьміть предмет i інакше Кожна комірка потребує лише рядок безпосередньо над нею, тому весь таблицю можна заповнити рядками зліва направо, по одному, за часом O(n·W), і якщо вам потрібна лише кінцева вартість, то O(W) місця можна використовувати, зберігаючи одну ковзну рядок (ітерується від великого w до малого w, тому кожен елемент використовується лише один раз). Остання комірка, dp[n][W], є відповіддю.

dp[0][w] = 0                                    for all w   (no items yet)

dp[i][w] = dp[i-1][w]                            if weight[i] > w   (must skip — too heavy)

dp[i][w] = max( dp[i-1][w],                      // skip item i
                dp[i-1][w - weight[i]] + value[i] )  // take item i
                                                  otherwise

жива демонстрація · пов'язана симуляція● LIVE

Відстеження шляхів для відновлення фактичних предметів

Таблиця надає оптимальне значення, але зазвичай ви також хочете знати, які саме предмети потрібно запакувати. Починаючи з dp[n][W], порівняйте його зі значенням dp[n-1][W]: якщо вони рівні, предмет n не був потрібним, тому перейдіть до dp[n-1][W] і повторіть; якщо вони відрізняються, предмет n обов’язково було взяти, тому зафіксуйте його та перейдіть до dp[n-1][W - вага[n]]. Повторюючи це до dp[0][0], ви відновлюєте точний оптимальний набір предметів, в O(n) додаткових кроках після побудови таблиці.

Чому жадібний підхід тут не спрацьовує

Зрозумілою природною спробою є сортування предметів за співвідношенням вартість до маси та жадібне вилучення найкращого співвідношення, поки воно ще вміщується. Це доведено як оптимально для часткового рюкзака, де предмети можна розділити – але для рюкзака 0/1 це може бути абсолютно поганим. Один приклад показує це: з ємністю 10 і двома предметами, один важить 6 і коштує 6 (відношення 1.0) та інший важить 5 і коштує 5.5, а третій важить 5 і коштує 5.5 (відношення 1.1 кожний). Жадібний підхід вибирає предмет з трохи гіршим співвідношенням... основна проблема завжди однакова: жадібний робить раннє рішення, зосереджуючись на тому предметі, який здається найкращим окремо, і може залишити ємність невикористаною, яку інша комбінація б використала повністю, тоді як рекурсивне DP правильно порівнює кожну комбінацію опосередковано через її двохетапну рекурсію.

Коли сама таблиця стає вузьким місцем

Час виконання O(n·W) обманливо: він виглядає поліноміальним у розмірі вхідних даних, але W - це число, і вхідним данім потрібно приблизно log₂(W) біт для кодування їх — алгоритм є псевдополіноміальним. Для здатності до кількох тисяч це миттєво; для здатності до мільярдів, таблиця стає неможливо великою, навіть якщо n відносно невелика. Реальні логістичні та фінансові застосунки з величезними ємностями або постійними вагами замість цього перемикаються на метод branch-and-bound, meet-in-the-middle для помірного n, або схеми апроксимації, які обмінюються невеликою, доведеною межею втратою оптимальності за рахунок розв'язання.

Часті запитання

Чому жадібний підхід — завжди брати елемент з найбільшим співвідношенням вага/ціна — не спрацьовує на сумці 0/1?

Це пов'язано з тим, що ви не можете взяти частину елемента. Жадібний алгоритм може заповнити ємність суми висококоефіцієнтною позицією, залишаючи незручну кількість вільного простору, що призводить до втрати місця, яке іншою, дещо менш коефіцієнтною комбінацією було б використано повністю. Це працює для варіанту з частковою сумкою, де елементи можна розділити, але не для 0/1.

Чи є динамічне програмування рішення для суми 0/1 ефективним у строгому сенсі?

Воно працює за часом O(n·W), що виглядає як поліноміальний час, але насправді ні, оскільки W — це число, а не розмір вхідних даних — для запису вхідних даних потрібно лише log(W) біт. Це називається псевдополіноміальним часом, і саме тому таблиця DP стає недоцільно великою, коли ємності досягають мільйонів, навіть якщо вона повністю обчислювана для невеликих ємностей, які зазвичай використовуються в навчальних прикладах.

Які зміни відбуваються, якщо дозволено брати кілька копій одного й того самого елемента?

Це задача з необмеженою сумкою, і для її вирішення потрібно лише одна-строкова зміна рекуренції: при розгляді елементу ви дозволяєте собі повторно використовувати поточний рядок замість тільки попереднього, оскільки взяти одну копію не забороняє взяти іншу. Обмеження 0/1 зникає, і DP все ще працює приблизно в псевдополіноміальному часі.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте 0/1 Knapsack і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.

▶ Відкрити симуляцію 0/1 Knapsack

0/1 Knapsack: Динамічне Програмування, Клітинка за Клітиною