Перегляд вихідного коду сторінки Задача пакування рюкзака

[[Файл:Knapsack.svg|thumb|Приклад одновимірної задачі (з обмеженням) про пакування рюкзака: Як підібрати коробки так, щоб їхня вартість була максимальною, а сумарна вага не більше 15 кг? (''Розв'язок'': Якщо доступна достатня кількість екземплярів кожної коробки, то пакується три жовті коробки та три сірі коробки; якщо наявні лише ті, що зображені на малюнку, то пакуються всі, крім зеленої коробки.)]]
'''Задача пакування рюкзака''' ({{lang-en|Knapsack problem}})&nbsp;— задача [[комбінаторна оптимізація|комбінаторної оптимізації]]: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити [[рюкзак]], що здатен витримати деяку максимальну масу, предметами, кожен з яких має [[вартість]] (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу.

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

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

== Історія ==
Задача про пакування рюкзаку досліджується вже понад століття. Відома згадка ще 1897 року в статті {{Нп|Джордж Метьюз Баллард|Джорджа Метьюза Балларда||George Ballard Mathews}}<ref>{{cite journal | title = On the partition of numbers | author = Mathews, G. B. | journal = Proceedings of the London Mathematical Society | volume = 28 | pages = 486&ndash;490 | date = 25 June 1897 | url = http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf | doi = 10.1112/plms/s1-28.1.486 | accessdate = 26 липня 2019 | archive-date = 26 травня 2012 | archive-url = https://web.archive.org/web/20120526165606/http://plms.oxfordjournals.org/content/s1-28/1/486.full.pdf }}</ref>. Сама назва «задача про пакування рюкзаку» відсилає до ранніх робіт математика {{Нп|Тобіас Данциг|Тобіаса Данцига||Tobias Dantzig}} (1884—1956)<ref>Dantzig, Tobias. Numbers: The Language of Science, 1930.</ref>, і стосується звичайної проблеми пакування найбільш цінних або корисних речей без перевантаження.

Інтенсивне дослідження проблеми почалось з середини ХХ століття і в 1972 році була включена [[Річард Карп|Річардом Карпом]] ({{lang-en|Richard Karp}})
до списку [[21 NP-повна задача Карпа|21 NP-повної задачі]]<ref>{{cite book
 |author       = Richard M. Karp
 |author-link  = Річард Карп
 |chapter      = Reducibility Among Combinatorial Problems
 |chapter-url  = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 |title        = Complexity of Computer Computations
 |editor       = R. E. Miller
 |editor2      = J. W. Thatcher
 |editor3      = J.D. Bohlinger
 |publisher    = New York: Plenum
 |pages        = 85–103
 |year         = 1972
 |doi          = 10.1007/978-1-4684-2001-2_9
 |ref          = harv
 |accessdate   = 26 липня 2019
 |archive-date = 10 лютого 2021
 |archive-url  = https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
}}</ref>.

== Застосування ==
Дослідження 1998 року проведене [http://www.cs.sunysb.edu/~algorith/ репозитарієм алгоритмів] {{Webarchive|url=https://web.archive.org/web/20091128205537/http://www.cs.sunysb.edu/~algorith/ |date=28 листопада 2009 }} [[Університет штату Нью-Йорк у Стоуні-Брук|університету Стоні Брук]] показало, що з 75 алгоритмічних задач, задача пакування рюкзака була 19-ю за по популярністю і 3-ю з найбільш необхідних після таких задач, як [[суфіксне дерево]] та [[задача про пакування в ємності]]<ref>{{cite journal | title = Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository | author = Skiena, S. S. |journal = ACM SIGACT News | volume = 30 | issue=3 |date = September 1999| pages= 65&ndash;74  |issn=0163-5700 | doi=10.1145/333623.333627| citeseerx = 10.1.1.41.8357 }}</ref>.

Задачу пакування рюкзака використовують для моделювання різних проблем, зокрема:
* У системах підтримки [[Інвестиційний портфель|управління портфелем]] для балансування та диверсифікації вибраних капіталовкладень із метою пошуку найкращого балансу між ризиками та ефективністю вкладів у різні [[Інвестиція|фінансові активи]]{{sfn|Kellerer, Pferschy, and Pisinger|2004|p=461}} та для [[Сек'юритизація активів|сек'юритизації активів]]{{sfn|Kellerer, Pferschy, and Pisinger|2004|p=465}};
* Генерування ключів для [[Ранцева криптосистема Меркле — Геллмана|криптосистем Меркле&nbsp;— Геллмана]]{{sfn|Kellerer, Pferschy, and Pisinger|2004|p=472}} та інших {{Нп|Ранцева криптосистема|криптосистем||Knapsack cryptosystems}}.

Також задача пакування рюкзака виникає у великій кількості промислових задач{{sfn|Silvano|1990|p=2}}{{sfn|Бурков, Горгидзе, Ловецкий|1974|p=217}}:
* У {{Нп|Задача кроєння|кроєнні різних матеріалів||Cutting stock problem}} (тканини, сталеві листи тощо): вибір оптимальної схеми розкрою матеріалів з метою зменшення кількості відходів{{sfn|Kellerer, Pferschy, and Pisinger|2004|p=449}};
* При завантаженні човна або літака: вибір багажів для оптимального завантаження транспортного засобу;
* При розміщенні вантажів на складі мінімальної площі.

Одним із перших застосувань алгоритмів пакування рюкзака була створення та оцінка тестів, в яких тестовані особи мали вибір, на які питання вони будуть відповідати. При невеликій кількості прикладів це доволі прозорий процес. Наприклад, якщо іспит містить 12 запитань кожен з яких на 10 балів, тестованій особі потрібно відповісти лише на 10 запитань для досягнення максимально можливої оцінки&nbsp;— 100 балів. Проте, якщо тестові завдання дають різну кількість балів, зробити вибір вже важче. Фюерман і Вайс запропонували систему, в якій студентам дають гетерогенний тест із загальною кількістю 125 можливих балів. Студентів просять відповісти на всі питання, наскільки це можливо. З усіх можливих підмножин завдань, загальні значення яких дорівнюють або не перевищують 100, алгоритм визначає, який піднабір дасть кожному студенту найвищий можливий бал<ref>{{cite journal | title = A Mathematical Programming Model for Test Construction and Scoring | url = https://archive.org/details/sim_management-science_1973-04_19_8/page/961 | journal = Management Science | volume = 19 | issue = 8 |date = April 1973|pages = 961–966 |author1=Feuerman, Martin |author2=Weiss, Harvey | jstor = 2629127 | doi=10.1287/mnsc.19.8.961}}</ref>.

== Постановка задачі ==
{{seealso|[[Список задач про наповнення рюкзака]]}}
Задачу пакування рюкзака можна визначити засобами математичного апарату. Нехай кожному об'єктові для пакування зіставлено індекс ''i'', який приймає значення від ''1'' до ''n''. Числа <math>w_i</math> та <math>p_i</math> відповідають вазі та вартості об'єкта ''i''. Максимальна припустима маса, яку здатен витримати рюкзак, дорівнює ''W''.

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

Існує багато варіантів заповнення рюкзака. Для описання окремого варіанту пакування необхідно вказати для кожного об'єкта, чи його обрано (запаковано). Для цього можна використати двійковий [[вектор]] <math>X=(x_1, x_2, \dots , x_n)</math>, компонента <math>x_i</math> якого дорівнюватиме ''1'', якщо ''i''-тий об'єкт запаковано, та ''0'' якщо ні. Цей вектор називається ''вектором заповнення''. Вагу та вартість запакованих предметів, можна обчислити як [[функція (математика)|функцію]] від вектора заповнення.

Для заданого вектора заповнення ''X'' вартість предметів запакованих у рюкзак дорівнює:
: <math>z(X) = \sum_{\{i, \, x_i=1\}} p_i = \sum_{i=1}^n x_ip_i</math>
Аналогічно, загальна маса предметів дорівнює:
: <math>w(X) = \sum_{i=1}^n x_iw_i </math>

Таким чином, задача пакування рюкзака полягає у відшуканні такого вектора заповнення <math>X=(x_1, x_2, \dots, x_n)</math>, що максимізує функцію <math>z(X)</math> за умови:
: <math>w(X)=\sum_{i=1}^n x_iw_i \leqslant W</math> (1)
Тобто, загальна маса обраних предметів <math>w(X)</math> не перевищує можливості рюкзака <math>W</math>.

Взагалі, діють такі додаткові умови:
* <math>\sum_{i=1}^n w_i > W</math>: всі доступні об'єкти не можливо покласти до рюкзака разом;
* <math>p_i > 0, \forall i \in \{1, \dots, n\}</math> : будь-який додатковий об'єкт надає перевагу;
* <math>w_i > 0, \forall i \in \{1, \dots, n\}</math> : будь-який об'єкт використовує ресурси.

Термінологія:
* Функція <math>z(X)</math>&nbsp;— називається ''[[Цільова функція|цільовою]]'';
* Будь-який вектор <math>X</math>, що відповідає умові (1), називається ''припустимим'';
* Якщо вартість <math>z(X)</math> максимальна, то вектор <math>X</math> називається ''оптимальним''.

Припустімо, окрім вартості предмети мають ще одну характеристику (наприклад, щільність). Задача пошуку вектора заповнення <math>X</math>, що максимізує обидві функції (сумарна вартість та сумарна щільність) є ''[[Багатокритеріальна оптимізація|багатокритеріальним]] варіантом 0-1 задачі пакування рюкзака''.<ref>{{Cite book 
| author =Matthias Ehrgott
| title = Multicriteria Optimization
| date = 2005
| publisher = Springer
| isbn = 3-540-21398-8}}</ref>

'''Обмежена задача пакування рюкзака''' обмежує кількість <math>x_i</math> копій кожного виду предмета максимальним цілим значенням <math>k_i</math>. Математично цю задачу можна сформулювати так:
* максимізувати <math>\qquad \sum_{i=1}^n p_ix_i</math>
* за умови <math>\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots,k_i\}</math>

'''Необмежена задача пакування рюкзака''' ('''НЗПР''') не накладає верхньої межі для кількості копій кожного виду предмета. Тобто потрібно
* максимізувати <math>\qquad \sum_{i=1}^n p_ix_i</math>
* за умови <math>\qquad \sum_{i=1}^n w_ix_i \leqslant W, \quad \quad x_i \in \{0,1,\ldots\}</math>

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

Особливий інтерес представляє окремий випадок задачі пакування рюкзака з такими властивостями:
* вона є [[проблема вибору|проблемою вибору]],
* вона є 0-1 задачею,
* для кожного виду предмета вага дорівнює вартості: <math>w_i=p_i</math>.
У цьому разі задача еквівалентна такій задачі: задано множину невід'ємних цілих чисел, чи існує будь-яка її підмножина, сума елементів якої складає точно ''W''? Або, якщо допускається від'ємна вага і ''W'' дорівнює нулю, то задачею є: задано множину цілих чисел, чи існує непорожня підмножина, сума елементів якої точно дорівнює 0? Цей окремий випадок називається [[Задача про суму підмножини|задачею суми підмножини]]. У галузі криптографії термін ''задача пакування рюкзака'' часто використовується для позначення конкретно задачі суми підмножини.

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

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

Задачу пакування рюкзака можна описати термінами [[теорія множин|теорії множин]].<ref name="lagoudakis">{{ref-en}} Michail G. Lagoudakis, [http://www2.isye.gatech.edu/~mlagouda/acadpape.html The 0-1 Knapsack Problem&nbsp;— An Introductory Survey] {{Webarchive|url=https://web.archive.org/web/20081203120000/http://www2.isye.gatech.edu/~mlagouda/acadpape.html}}, 1996.</ref>

Нехай задано множину об'єктів <math>U</math>, вагу <math>w(u) \in Z^+</math>, та вартість <math>z(u) \in Z^+</math> для кожного об'єкта <math>u \in U</math> та максимальну припустиму вагу <math>W</math>. Необхідно знайти [[підмножина|підмножину]] <math>U'</math>, таку, щоб:
: <math>\sum_{u\in U'} w(u) \leqslant W</math> та <math>\sum_{u\in U'} p(u) = max</math>.

== Обчислювальна складність ==
{{seealso|NP-складна задача|NP-повна задача}}

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

Представлення у вигляді задачі розпізнавання запроваджує додатковий параметр ''P''&nbsp;— бажана вартість предметів у рюкзаку та ставить запитання чи існує ще один варіант пакування, з сумарною вартістю запакованих предметів більшою за ''P''.<ref name="lagoudakis"/> Мета запровадження задачі розпізнавання полягає в тому, що з точки зору теорії обчислювальної складності та NP-повноти для неї легше визначати складність. Якщо [[Цільова функція|цільову функцію]] не складно обчислювати, то задача розпізнавання не складніша за відповідну задачу оптимізації. Таким чином, із NP-повноти задачі розпізнавання випливає NP-повнота задачі оптимізації.<ref>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.</ref><ref name="lagoudakis"/>

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

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

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

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

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

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

=== Жадібний алгоритм ===
[[Файл:Knapsack greedy.svg|thumb|Дві фази жадібного алгоритму: Ліворуч: впорядкування предметів за їхньою ефективністю (в цьому разі, вартість на кіло ваги). Праворуч: пакування в рюкзак, якщо є можливість. Отриманий розв'язок дає $11 та 11&nbsp;кг, в той час як оптимальний $12 та 14&nbsp;кг.]]

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

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

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

<!--

==== Аналіз ефективності алгоритму ====

=== Метаевристики ===

==== Генетичний алгоритм ====

==== Алгоритми засновані на мурашиних колоніях ====
-->

== Точні методи ==
Класична задача пакування рюкзака була вивчена досить глибоко. Існує багато методів пошуку точних розв'язків задачі. Більшість з них є покращеними варіантами одного з наведених нижче методів пошуку точного розв'язку задачі. А саме використовується підхід динамічне програмування<ref name="eduk2000">{{cite journal | last1 = Andonov | first1 = Rumen | last2 = Poirriez | first2 = Vincent | last3 = Rajopadhye | first3 = Sanjay | year = 2000 | title = Unbounded Knapsack Problem : dynamic programming revisited | url = http://www.univ-valenciennes.fr/limav/poirriez/pub/rech/PI-1152.ps.gz | journal = European Journal of Operational Research | volume = 123 | issue = 2 | pages = 168–181 | doi = 10.1016/S0377-2217(99)00265-9 | citeseerx = 10.1.1.41.2135 | accessdate = 28 липня 2019 | archive-date = 29 січня 2020 | archive-url = https://web.archive.org/web/20200129053304/http://www.uphf.fr/limav/poirriez/pub/rech/PI-1152.ps.gz }}</ref>, метод гілок і меж<ref name="martellototh90">S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations,
John Wiley and Sons, 1990</ref> або {{Нп|Гібридний алгоритм|гібридне поєднання||Hybrid algorithm}} обох підходів.<ref name="poirriez_et_all_2009">{{cite journal|last1=Poirriez|first1=Vincent|last2=Yanev|first2=Nicola|last3=Andonov|first3=Rumen|title=A hybrid algorithm for the unbounded knapsack problem|journal=Discrete Optimization|volume=6|issue=1|year=2009|pages=110–124|issn=1572-5286|doi=10.1016/j.disopt.2008.09.004}}</ref><ref name="martellopisingertoth99a">S. Martello, D. Pisinger, P. Toth, [https://www.jstor.org/stable/pdf/2634886.pdf?casa_token=wd6Ykeu46i0AAAAA:egeiDBT-4ijIpmM5GUKA8Ywc67SyXsHHCpFR3QlIL5GGDvx546hVIjk9vbeJsgfh_1NyDcH8EMh9TkBoqRHvMHA8xtT4uUzG5x2mZJ4FzCE_wC0mEhp0Tg Dynamic programming and strong bounds for the 0-1 knapsack problem], ''Manag. Sci.'', 45:414–424, 1999.</ref><ref name="plateau85">{{cite journal | last1 = Plateau | first1 = G. | last2 = Elkihel | first2 = M. | year = 1985 | title = A hybrid algorithm for the 0-1 knapsack problem | url = | journal = Methods of Oper. Res. | volume = 49 | issue = | pages = 277–293 }}</ref><ref name="martellotothe99">{{cite journal | last1 = Martello | first1 = S. | last2 = Toth | first2 = P. | year = 1984| title = A mixture of dynamic programming and branch-and-bound for the subset-sum problem | url = | journal = Manag. Sci. | volume = 30 | issue = 6| pages = 765–771 | doi=10.1287/mnsc.30.6.765}}</ref>

=== Динамічне програмування ===
{{Main|Динамічне програмування}}

Задача пакування рюкзака має властивість ''суб-оптимальної структури'', тобто, можна знайти оптимальний розв'язок задачі з <math>i</math> змінними на основі розв'язку задачі з <math>i-1</math> змінною. Ця властивість дозволяє застосувати засоби [[динамічне програмування|динамічного програмування]] для розв'язання задачі пакування рюкзака.

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

Ідея полягає в тому, що оптимальний розв'язок задачі ''KP(i,&nbsp;c)'' можна отримати, використовуючи розв'язки двох простіших задач:
* задачі з <math>i-1</math> змінними для рюкзака з такою ж ємністю ''c'' (''KP(i−1, c)''), та <math>x_i = 0</math>;
* задачі з <math>i-1</math> змінними для рюкзака з ємністю <math>c - w_i</math> (<math>KP(i-1, c - w_i)</math>), та <math>x_i = 1</math>.

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

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

* <math>KP(0,\,c)=0, \quad 0 \le c \le W </math>
* <math>KP(i,\,0)=0, \quad 0 \le i \le n </math>
* <math>KP(i,\,c)=KP(i-1,\,c)</math>, якщо <math>w_i > c\,\!</math> (новий предмет важчий, ніж поточний резерв ваги)
* <math>KP(i,\,c)=\max(KP(i-1,\,c),\,KP(i-1,c-w_i)+p_i)</math>, якщо <math>w_i \leqslant c</math>.

Потім будується таблиця 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]<nowiki></nowiki>] + p[i] )
     '''інакше'''
       T[i,c] := T[i-1,c]
     '''кінець якщо'''
   '''кінець для'''
 '''кінець для'''
 '''вивести''' T[n,W]

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

[[Часова складність алгоритму]] дорівнює <math>O(nW)</math>. Алгоритм має дві переваги:
# Швидкість;
# Не потрібне сортування змінних.
та недолік:
# вимагає порівняно багато пам'яті (що робить його не прийнятним для розв'язання великих задач).

Цей метод було розроблено [[Роберт Шон Ґарфінкель|Робертом Ґарфінкелем]] та {{Нп|Джордж Немгаузер|Джорджем Немгаузером||George Nemhauser}} в 1972 році.<ref>{{ref-en}} R. S. Garfinkel et G. L. Nemhauser. ''Integer Pogramming''. John Wiley & Sons, New York, 1972. ISBN 0-471-29195-1.</ref>
<!--

=== Порядок розподілу та оцінки ===

=== Гібрідний підхід ===

== Варіанти задачі ==
-->

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

Подібно до інших задач комбінаторної оптимізації, задача пакування рюкзака може бути розв'язана [[метод гілок і меж|методом гілок і меж]] ({{lang-en|Branch-and-bound algorithm}}). Застосування методу гілок і меж до розв'язання задачі пакування рюкзака вперше запропонував Колесар в 1967 році. Варіант алгоритму розроблений Грінбергом та Хегерічем в 1970 році мав істотно нижчі вимоги до пам'яті та часу. Горовіц та Сані в 1974 році запропонували свій алгоритм побудований на основі попередніх варіантів. Цей алгоритм найефективніший та найпростіший для реалізації у порівнянні з попередніми алгоритмами. Запропонований Мартело та Тозом алгоритм<ref name="martello_toth_90">{{ref-en}} Silvano Martello et Paolo Toth, ''Knapsack Problems: Algorithms and Computer Implementations'', John Wiley & Sons, 1990 ISBN 0-471-92420-2.</ref> набув значного поширення. Перевагою цього методу є низькі вимоги до обсягів необхідної пам'яті.

== Примітки ==
{{reflist}}

== Література ==
* Hans Kellerer, Ulright Pferschy and David Pisinger, ''Knapsack Problems'', Springer, 2004 ISBN 3-540-40286-1. {{ref-en}}
* Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163—166, 1985. {{ref-en}}

== Див. також ==
{{Портал|Математика}}
* [[Список задач про наповнення рюкзака]]
* [[21 NP-повна задача Карпа]]
* [[Комбінаторна оптимізація]]
* [[Задача про пакування в ємності]]
* [[Задача комівояжера]]

== Посилання ==
* [http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf Динамічне програмування. 0-1 задача пакування рюкзака] {{Webarchive|url=https://web.archive.org/web/20120216072115/http://www.cse.unl.edu/~goddard/Courses/CSCE310J/Lectures/Lecture8-DynamicProgramming.pdf |date=16 лютого 2012 }} (слайди лекції) {{ref-en}}
* [http://logic.pdmi.ras.ru/~kulikov/simplealgscourse/lecture7-slides.pdf Слайди лекції з динамічного програмування] {{Webarchive|url=https://web.archive.org/web/20090419062718/http://logic.pdmi.ras.ru/~kulikov/simplealgscourse/lecture7-slides.pdf |date=19 квітня 2009 }} (п.4. Задача пакування рюкзака). {{ref-ru}}

{{NP-повні задачі}}
[[Категорія:Дослідження операцій]]
[[Категорія:Динамічне програмування]]