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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Задача пакування рюкзака: Як підібрати коробки так, щоб їхня вартість була максимальною, а сумарна вага не більше 15 кг?

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

Історія[ред.ред. код]

Дослідження[ред.ред. код]

Задача пакування рюкзака є однією з 21 NP-повних задач Ричарда Карпа (англ. Richard Karp) викладених в його статті 1972 року. Інтенсивне дослідження проблеми почалось з середини ХХ століття але відома згадка ще в 1897 році, в статті Джорджа Метьюза Балларда [1]. Описання задачі досить просте, але розв'язання — складне. Існуючі алгоритми, на практиці, здатні розв'язати задачі досить великих розмірів. Однак, унікальна структура задачі, а також той факт, що вона присутня як підзадача у більших, загальніших проблемах, робить її важливою для наукових досліджень.

Застосування[ред.ред. код]

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

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

Також дослідження цієї задачі корисне для пошуку розв'язків методом генерування стовпчиків та в задачі завантаження контейнерів.

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

Постановка задачі[ред.ред. код]

Задачу пакування рюкзака можна визначити засобами математичного апарату. Нехай кожному об'єктові для пакування зіставлено індекс 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_ip_i

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

w(X) = \sum_{i=1}^n x_iw_i

Таким чином, задача пакування рюкзака полягає у відшуканні такого вектора заповнення X=(x_1, x_2, \dots, x_n), що максимізує функцію z(X) за умови:

w(X)=\sum_{i=1}^n x_iw_i \le 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 задачі пакування рюкзака.[2]

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

  • максимізувати \qquad \sum_{i=1}^n p_ix_i
  • за умови \qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots,k_i\}

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

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

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

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

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

Формулювання засобами теорії множин[ред.ред. код]

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

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

\sum_{u\in U'} w(u) \le W та \sum_{u\in U'} p(u) = max.

NP-складність[ред.ред. код]

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

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

\sum_{u\in U'} w(u) \le W, та \sum_{u\in U'} z(u) \ge P?

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

Як і для інших 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 задачу пакування рюкзака. Позначимо через 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 \le c \le W
  • KP(i,\,0)=0, \quad 0 \le i \le 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 році.[5]

Метод гілок і меж[ред.ред. код]

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. (англ.) G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.
  2. Matthias Ehrgott (2005). Multicriteria Optimization. Springer. ISBN 3-540-21398-8. 
  3. а б в (англ.) Michail G. Lagoudakis, The 0-1 Knapsack Problem - An Introductory Survey, 1996.
  4. Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Comp., San Francisco, 1979.
  5. (англ.) R. S. Garfinkel et G. L. Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1.
  6. (англ.) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 ISBN 0-471-92420-2.
  • (англ.) 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.

Посилання[ред.ред. код]