Задача пакування рюкзака

Приклад одновимірної задачі (з обмеженням) про пакування рюкзака: Як підібрати коробки так, щоб їхня вартість була максимальною, а сумарна вага не більше 15 кг? (Розв'язок: Якщо доступна достатня кількість екземплярів кожної коробки, то пакується три жовті коробки та три сірі коробки; якщо наявні лише ті, що зображені на малюнку, то пакуються всі, крім зеленої коробки.)

Задача пакування рюкзака (англ. Knapsack problem) — задача комбінаторної оптимізації: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити рюкзак, що здатен витримати деяку максимальну масу, предметами, кожен з яких має вартість (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу.

Задача часто виникає при розподілі ресурсів, коли наявні фінансові обмеження, і вивчається в таких областях, як комбінаторика, інформатика, теорія складності, криптографія, прикладна математика.

Описання задачі досить просте, але розв'язання — складне. Відомі алгоритми, на практиці, здатні розв'язати задачі досить великих розмірів. Однак, унікальне формулювання задачі, а також той факт, що вона присутня як підзадача у більших, загальніших проблемах, робить її важливою для наукових досліджень.

Історія

Задача про пакування рюкзаку досліджується вже понад століття. Відома згадка ще 1897 року в статті Джорджа Метьюза Балларда. Сама назва «задача про пакування рюкзаку» відсилає до ранніх робіт математика Тобіаса Данцига (1884—1956), і стосується звичайної проблеми пакування найбільш цінних або корисних речей без перевантаження.

Інтенсивне дослідження проблеми почалось з середини ХХ століття і в 1972 році була включена Річардом Карпом (англ. Richard Karp) до списку 21 NP-повної задачі.

Застосування

Дослідження 1998 року проведене репозитарієм алгоритмів [Архівовано 28 листопада 2009 у Wayback Machine.] університету Стоні Брук показало, що з 75 алгоритмічних задач, задача пакування рюкзака була 19-ю за по популярністю і 3-ю з найбільш необхідних після таких задач, як суфіксне дерево та задача про пакування в ємності.

Задачу пакування рюкзака використовують для моделювання різних проблем, зокрема:

• У системах підтримки управління портфелем для балансування та диверсифікації вибраних капіталовкладень із метою пошуку найкращого балансу між ризиками та ефективністю вкладів у різні фінансові активи та для сек'юритизації активів;
• Генерування ключів для криптосистем Меркле — Геллмана та інших криптосистем.

Також задача пакування рюкзака виникає у великій кількості промислових задач:

• У кроєнні різних матеріалів (тканини, сталеві листи тощо): вибір оптимальної схеми розкрою матеріалів з метою зменшення кількості відходів;
• При завантаженні човна або літака: вибір багажів для оптимального завантаження транспортного засобу;
• При розміщенні вантажів на складі мінімальної площі.

Одним із перших застосувань алгоритмів пакування рюкзака була створення та оцінка тестів, в яких тестовані особи мали вибір, на які питання вони будуть відповідати. При невеликій кількості прикладів це доволі прозорий процес. Наприклад, якщо іспит містить 12 запитань кожен з яких на 10 балів, тестованій особі потрібно відповісти лише на 10 запитань для досягнення максимально можливої оцінки — 100 балів. Проте, якщо тестові завдання дають різну кількість балів, зробити вибір вже важче. Фюерман і Вайс запропонували систему, в якій студентам дають гетерогенний тест із загальною кількістю 125 можливих балів. Студентів просять відповісти на всі питання, наскільки це можливо. З усіх можливих підмножин завдань, загальні значення яких дорівнюють або не перевищують 100, алгоритм визначає, який піднабір дасть кожному студенту найвищий можливий бал.

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

Задачу пакування рюкзака можна визначити засобами математичного апарату. Нехай кожному об'єктові для пакування зіставлено індекс i, який приймає значення від 1 до n. Числа $w_{i}$ та $p_{i}$ відповідають вазі та вартості об'єкта i. Максимальна припустима маса, яку здатен витримати рюкзак, дорівнює W.

0-1 задача пакування рюкзака

Існує багато варіантів заповнення рюкзака. Для описання окремого варіанту пакування необхідно вказати для кожного об'єкта, чи його обрано (запаковано). Для цього можна використати двійковий вектор $X=(x_{1},x_{2},\dots ,x_{n})$, компонента $x_{i}$ якого дорівнюватиме 1, якщо i-тий об'єкт запаковано, та 0 якщо ні. Цей вектор називається вектором заповнення. Вагу та вартість запакованих предметів, можна обчислити як функцію від вектора заповнення.

Для заданого вектора заповнення X вартість предметів запакованих у рюкзак дорівнює:

$z(X)=\sum _{\{i,\,x_{i}=1\}}p_{i}=\sum _{i=1}^{n}x_{i}p_{i}$

Аналогічно, загальна маса предметів дорівнює:

$w(X)=\sum _{i=1}^{n}x_{i}w_{i}$

Таким чином, задача пакування рюкзака полягає у відшуканні такого вектора заповнення $X=(x_{1},x_{2},\dots ,x_{n})$, що максимізує функцію $z(X)$ за умови:

$w(X)=\sum _{i=1}^{n}x_{i}w_{i}\leqslant W$ (1)

Тобто, загальна маса обраних предметів $w(X)$ не перевищує можливості рюкзака $W$.

Взагалі, діють такі додаткові умови:

• $\sum _{i=1}^{n}w_{i}>W$: всі доступні об'єкти не можливо покласти до рюкзака разом;
• $p_{i}>0,\forall i\in \{1,\dots ,n\}$ : будь-який додатковий об'єкт надає перевагу;
• $w_{i}>0,\forall i\in \{1,\dots ,n\}$ : будь-який об'єкт використовує ресурси.

Термінологія:

• Функція $z(X)$ — називається цільовою;
• Будь-який вектор $X$, що відповідає умові (1), називається припустимим;
• Якщо вартість $z(X)$ максимальна, то вектор $X$ називається оптимальним.

Припустімо, окрім вартості предмети мають ще одну характеристику (наприклад, щільність). Задача пошуку вектора заповнення $X$, що максимізує обидві функції (сумарна вартість та сумарна щільність) є багатокритеріальним варіантом 0-1 задачі пакування рюкзака.

Обмежена задача пакування рюкзака обмежує кількість $x_{i}$ копій кожного виду предмета максимальним цілим значенням $k_{i}$. Математично цю задачу можна сформулювати так:

• максимізувати $\qquad \sum _{i=1}^{n}p_{i}x_{i}$
• за умови $\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad \quad x_{i}\in \{0,1,\ldots ,k_{i}\}$

Необмежена задача пакування рюкзака (НЗПР) не накладає верхньої межі для кількості копій кожного виду предмета. Тобто потрібно

• максимізувати $\qquad \sum _{i=1}^{n}p_{i}x_{i}$
• за умови $\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad \quad x_{i}\in \{0,1,\ldots \}$

Приклад такої задачі наведена на малюнку у вступній частині (див. текст «Якщо доступна достатня кількість екземплярів кожної коробки…»)

Особливий інтерес представляє окремий випадок задачі пакування рюкзака з такими властивостями:

• вона є проблемою вибору,
• вона є 0-1 задачею,
• для кожного виду предмета вага дорівнює вартості: $w_{i}=p_{i}$.

У цьому разі задача еквівалентна такій задачі: задано множину невід'ємних цілих чисел, чи існує будь-яка її підмножина, сума елементів якої складає точно W? Або, якщо допускається від'ємна вага і W дорівнює нулю, то задачею є: задано множину цілих чисел, чи існує непорожня підмножина, сума елементів якої точно дорівнює 0? Цей окремий випадок називається задачею суми підмножини. У галузі криптографії термін задача пакування рюкзака часто використовується для позначення конкретно задачі суми підмножини.

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

Формулювання у термінах теорії множин

Задачу пакування рюкзака можна описати термінами теорії множин.

Нехай задано множину об'єктів $U$, вагу $w(u)\in Z^{+}$, та вартість $z(u)\in Z^{+}$ для кожного об'єкта $u\in U$ та максимальну припустиму вагу $W$. Необхідно знайти підмножину $U'$, таку, щоб:

$\sum _{u\in U'}w(u)\leqslant W$ та $\sum _{u\in U'}p(u)=max$.

Обчислювальна складність

Задача розпізнавання

Для оцінки алгоритмічної складності задачі, її оптимізаційне формулювання змінюють на задачу розпізнавання, яка є більш простою і тому може слугувати нижньою оцінкою складності.

Представлення у вигляді задачі розпізнавання запроваджує додатковий параметр P — бажана вартість предметів у рюкзаку та ставить запитання чи існує ще один варіант пакування, з сумарною вартістю запакованих предметів більшою за P. Мета запровадження задачі розпізнавання полягає в тому, що з точки зору теорії обчислювальної складності та NP-повноти для неї легше визначати складність. Якщо цільову функцію не складно обчислювати, то задача розпізнавання не складніша за відповідну задачу оптимізації. Таким чином, із NP-повноти задачі розпізнавання випливає NP-повнота задачі оптимізації.

Задача розпізнавання для оптимізаційної задачі 0-1 пакування рюкзака формулюється так: Задано скінченну множину U об'єктів, вагу $w(u)\in Z^{+}$, вартість $z(u)\in Z^{+}$ для кожного об'єкта $u\in U$ та цілі числа W (ємність рюкзака) та P (бажана вартість). Чи існує така підмножина $U'$, що:

$\sum _{u\in U'}w(u)\leq W$, та $\sum _{u\in U'}z(u)\geq P$?

Зв'язок з іншими задачами

Задача пакування рюкзака цікава з точки зору інформатики з багатьох причин:

• Задача пакування рюкзака у формі проблеми вибору (чи може бути досягнуто значення, щонайменше V, без перевищення ваги W?) є NP-повною, тому в загальному випадку не існує алгоритму як правильного, так і швидкого (який виконується за поліноміальний час).
• Хоча проблема вибору є NP-повною, проблема оптимізації є NP-складною, то вона, щонайменше, таке ж складна, як і проблема вибору, і тому не існує поліноміального алгоритму, який може визначити, чи є рішення оптимальним (це б означало, що не існує рішення, яке дає значення більше V, таким чином розв'язуючи NP-повну проблему вибору).
• Існує псевдополіноміальний алгоритм, який використовує динамічне програмування.
• Існує схема наближення до поліноміального часу, яка використовує наведений вище псевдополіноміальний алгоритм як підпрограму.
• У більшості випадків, що виникають на практиці, і для «випадкових екземплярів» з деяких ймовірнісних розподілів, все ж таки можуть бути розв'язані точно.

Наближені методи розв'язання

Як і для інших NP-повних задач, в деяких випадках достатньо знайти рішення, наближене до оптимального, але не обов'язково оптимальне. Бажано, також, щоб різниця між оптимальним розв'язком та знайденим була гарантованих розмірів.

Далі під ефективністю предмета розуміється відношення його вартості до ваги. Чим вище ефективність предмета, тим кориснішим він є для пакування.

Жадібний алгоритм

Дві фази жадібного алгоритму: Ліворуч: впорядкування предметів за їхньою ефективністю (в цьому разі, вартість на кіло ваги). Праворуч: пакування в рюкзак, якщо є можливість. Отриманий розв'язок дає $11 та 11 кг, в той час як оптимальний $12 та 14 кг.

Одним з найпростіших алгоритмів пошуку приблизного розв'язку є жадібний алгоритм. Ідея алгоритму полягає в тому, щоб класти до рюкзака в першу чергу найефективніші предмети, аж до його заповнення:

 впорядкувати предмети у порядку зменшення ефективності
 w_пак: = 0

 для i від 1 до n
   якщо w[i] + w_пак <= W тоді
     x[i] := 1
     w_пак := w_пак + w[i]
   інакше
     x[i] := 0
   кінець якщо
 кінець для

Точні методи

Класична задача пакування рюкзака була вивчена досить глибоко. Існує багато методів пошуку точних розв'язків задачі. Більшість з них є покращеними варіантами одного з наведених нижче методів пошуку точного розв'язку задачі. А саме використовується підхід динамічне програмування, метод гілок і меж або гібридне поєднання обох підходів.

Динамічне програмування

Задача пакування рюкзака має властивість суб-оптимальної структури, тобто, можна знайти оптимальний розв'язок задачі з $i$ змінними на основі розв'язку задачі з $i-1$ змінною. Ця властивість дозволяє застосувати засоби динамічного програмування для розв'язання задачі пакування рюкзака.

0-1 задача пакування рюкзака

Нехай потрібно розв'язати 0-1 задачу пакування рюкзака. Позначимо через KP(i, c) максимальну вартість, яку можна отримати для перших $i$ предметів із загальною вагою меншою або рівною c. Задача пакування рюкзака зводиться до знаходження KP(n, W).

Ідея полягає в тому, що оптимальний розв'язок задачі KP(i, c) можна отримати, використовуючи розв'язки двох простіших задач:

• задачі з $i-1$ змінними для рюкзака з такою ж ємністю c (KP(i−1, c)), та $x_{i}=0$;
• задачі з $i-1$ змінними для рюкзака з ємністю $c-w_{i}$ ($KP(i-1,c-w_{i})$), та $x_{i}=1$.

Розв'язок задачі пакування рюкзака з 0 змінними (KP (0 ,*)) дорівнює нулю. Розв'язок задачі пакування рюкзака при c=0 (KP (* ,0)) також дорівнює нулю.

Тепер можна записати $KP(i,c)$ рекурсивно:

• $KP(0,\,c)=0,\quad 0\leq c\leq W$
• $KP(i,\,0)=0,\quad 0\leq i\leq n$
• $KP(i,\,c)=KP(i-1,\,c)$, якщо $w_{i}>c\,\!$ (новий предмет важчий, ніж поточний резерв ваги)
• $KP(i,\,c)=\max(KP(i-1,\,c),\,KP(i-1,c-w_{i})+p_{i})$, якщо $w_{i}\leqslant c$.

Потім будується таблиця T[i, c], елементи якої містять значення розв'язків задач KP(i, c) в наступний спосіб:

для c від 0 до W робити
  T[0,c] := 0
кінець для

для i від 1 до n робити
  для c від 0 до W робити
    якщо c>=w[i] то
      T[i,c] := max( T[i-1,c], T[i-1, c-w[i]] + p[i] )
    інакше
      T[i,c] := T[i-1,c]
    кінець якщо
  кінець для
кінець для
вивести T[n,W]

Коли таблиця побудована, випадок задачі T[n, W] слід звести до випадку T[0, *].

Часова складність алгоритму дорівнює $O(nW)$. Алгоритм має дві переваги:

1. Швидкість;
2. Не потрібне сортування змінних.

та недолік:

1. вимагає порівняно багато пам'яті (що робить його не прийнятним для розв'язання великих задач).

Цей метод було розроблено Робертом Ґарфінкелем та Джорджем Немгаузером в 1972 році.

Метод гілок і меж

Подібно до інших задач комбінаторної оптимізації, задача пакування рюкзака може бути розв'язана методом гілок і меж (англ. Branch-and-bound algorithm). Застосування методу гілок і меж до розв'язання задачі пакування рюкзака вперше запропонував Колесар в 1967 році. Варіант алгоритму розроблений Грінбергом та Хегерічем в 1970 році мав істотно нижчі вимоги до пам'яті та часу. Горовіц та Сані в 1974 році запропонували свій алгоритм побудований на основі попередніх варіантів. Цей алгоритм найефективніший та найпростіший для реалізації у порівнянні з попередніми алгоритмами. Запропонований Мартело та Тозом алгоритм набув значного поширення. Перевагою цього методу є низькі вимоги до обсягів необхідної пам'яті.

Література

• Hans Kellerer, Ulright Pferschy and David Pisinger, Knapsack Problems, Springer, 2004 ISBN 3-540-40286-1. (англ.)
• Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163—166, 1985. (англ.)

Див. також

• Список задач про наповнення рюкзака
• 21 NP-повна задача Карпа
• Комбінаторна оптимізація
• Задача про пакування в ємності
• Задача комівояжера

Посилання

• Динамічне програмування. 0-1 задача пакування рюкзака [Архівовано 16 лютого 2012 у Wayback Machine.] (слайди лекції) (англ.)
• Слайди лекції з динамічного програмування [Архівовано 19 квітня 2009 у Wayback Machine.] (п.4. Задача пакування рюкзака). (рос.)