Задача пакування рюкзака (англ. Knapsack problem) — задача комбінаторної оптимізації: для заданої множини предметів, кожен з яких має вагу і цінність, визначити яку кількість кожного з предметів слід взяти, так, щоб сумарна вага не перевищувала задану, а сумарна цінність була максимальною. Задача бере свою назву від доволі відомої ситуації, коли потрібно наповнити рюкзак, що здатен витримати деяку максимальну масу, предметами, кожен з яких має вартість (або корисність) та масу. Необхідно обрати об'єкти в такий спосіб, аби максимізувати сумарну вартість (або користь), але не перевищити максимально припустиму масу.
Задача часто виникає при розподілі ресурсів, коли наявні фінансові обмеження, і вивчається в таких областях, як комбінаторика, інформатика, теорія складності, криптографія, прикладна математика.
Описання задачі досить просте, але розв'язання — складне. Відомі алгоритми, на практиці, здатні розв'язати задачі досить великих розмірів. Однак, унікальне формулювання задачі, а також той факт, що вона присутня як підзадача у більших, загальніших проблемах, робить її важливою для наукових досліджень.
Історія
Задача про пакування рюкзаку досліджується вже понад століття. Відома згадка ще 1897 року в статті [en]. Сама назва «задача про пакування рюкзаку» відсилає до ранніх робіт математика [en] (1884—1956), і стосується звичайної проблеми пакування найбільш цінних або корисних речей без перевантаження.
Інтенсивне дослідження проблеми почалось з середини ХХ століття і в 1972 році була включена Річардом Карпом (англ. Richard Karp) до списку 21 NP-повної задачі.
Застосування
Дослідження 1998 року проведене репозитарієм алгоритмів [ 28 листопада 2009 у Wayback Machine.] університету Стоні Брук показало, що з 75 алгоритмічних задач, задача пакування рюкзака була 19-ю за по популярністю і 3-ю з найбільш необхідних після таких задач, як суфіксне дерево та задача про пакування в ємності.
Задачу пакування рюкзака використовують для моделювання різних проблем, зокрема:
- У системах підтримки управління портфелем для балансування та диверсифікації вибраних капіталовкладень із метою пошуку найкращого балансу між ризиками та ефективністю вкладів у різні фінансові активи та для сек'юритизації активів;
- Генерування ключів для криптосистем Меркле — Геллмана та інших [en].
Також задача пакування рюкзака виникає у великій кількості промислових задач:
- У [en] (тканини, сталеві листи тощо): вибір оптимальної схеми розкрою матеріалів з метою зменшення кількості відходів;
- При завантаженні човна або літака: вибір багажів для оптимального завантаження транспортного засобу;
- При розміщенні вантажів на складі мінімальної площі.
Одним із перших застосувань алгоритмів пакування рюкзака була створення та оцінка тестів, в яких тестовані особи мали вибір, на які питання вони будуть відповідати. При невеликій кількості прикладів це доволі прозорий процес. Наприклад, якщо іспит містить 12 запитань кожен з яких на 10 балів, тестованій особі потрібно відповісти лише на 10 запитань для досягнення максимально можливої оцінки — 100 балів. Проте, якщо тестові завдання дають різну кількість балів, зробити вибір вже важче. Фюерман і Вайс запропонували систему, в якій студентам дають гетерогенний тест із загальною кількістю 125 можливих балів. Студентів просять відповісти на всі питання, наскільки це можливо. З усіх можливих підмножин завдань, загальні значення яких дорівнюють або не перевищують 100, алгоритм визначає, який піднабір дасть кожному студенту найвищий можливий бал.
Постановка задачі
Задачу пакування рюкзака можна визначити засобами математичного апарату. Нехай кожному об'єктові для пакування зіставлено індекс i, який приймає значення від 1 до n. Числа та відповідають вазі та вартості об'єкта i. Максимальна припустима маса, яку здатен витримати рюкзак, дорівнює W.
- 0-1 задача пакування рюкзака
Існує багато варіантів заповнення рюкзака. Для описання окремого варіанту пакування необхідно вказати для кожного об'єкта, чи його обрано (запаковано). Для цього можна використати двійковий вектор , компонента якого дорівнюватиме 1, якщо i-тий об'єкт запаковано, та 0 якщо ні. Цей вектор називається вектором заповнення. Вагу та вартість запакованих предметів, можна обчислити як функцію від вектора заповнення.
Для заданого вектора заповнення X вартість предметів запакованих у рюкзак дорівнює:
Аналогічно, загальна маса предметів дорівнює:
Таким чином, задача пакування рюкзака полягає у відшуканні такого вектора заповнення , що максимізує функцію за умови:
- (1)
Тобто, загальна маса обраних предметів не перевищує можливості рюкзака .
Взагалі, діють такі додаткові умови:
- : всі доступні об'єкти не можливо покласти до рюкзака разом;
- : будь-який додатковий об'єкт надає перевагу;
- : будь-який об'єкт використовує ресурси.
Термінологія:
- Функція — називається цільовою;
- Будь-який вектор , що відповідає умові (1), називається припустимим;
- Якщо вартість максимальна, то вектор називається оптимальним.
Припустімо, окрім вартості предмети мають ще одну характеристику (наприклад, щільність). Задача пошуку вектора заповнення , що максимізує обидві функції (сумарна вартість та сумарна щільність) є багатокритеріальним варіантом 0-1 задачі пакування рюкзака.
Обмежена задача пакування рюкзака обмежує кількість копій кожного виду предмета максимальним цілим значенням . Математично цю задачу можна сформулювати так:
- максимізувати
- за умови
Необмежена задача пакування рюкзака (НЗПР) не накладає верхньої межі для кількості копій кожного виду предмета. Тобто потрібно
- максимізувати
- за умови
Приклад такої задачі наведена на малюнку у вступній частині (див. текст «Якщо доступна достатня кількість екземплярів кожної коробки…»)
Особливий інтерес представляє окремий випадок задачі пакування рюкзака з такими властивостями:
- вона є проблемою вибору,
- вона є 0-1 задачею,
- для кожного виду предмета вага дорівнює вартості: .
У цьому разі задача еквівалентна такій задачі: задано множину невід'ємних цілих чисел, чи існує будь-яка її підмножина, сума елементів якої складає точно W? Або, якщо допускається від'ємна вага і W дорівнює нулю, то задачею є: задано множину цілих чисел, чи існує непорожня підмножина, сума елементів якої точно дорівнює 0? Цей окремий випадок називається задачею суми підмножини. У галузі криптографії термін задача пакування рюкзака часто використовується для позначення конкретно задачі суми підмножини.
Якщо допускається декілька рюкзаків, то задачу краще розглядати як задачу пакування в ємності.
Формулювання у термінах теорії множин
Задачу пакування рюкзака можна описати термінами теорії множин.
Нехай задано множину об'єктів , вагу , та вартість для кожного об'єкта та максимальну припустиму вагу . Необхідно знайти підмножину , таку, щоб:
- та .
Обчислювальна складність
Задача розпізнавання
Для оцінки алгоритмічної складності задачі, її оптимізаційне формулювання змінюють на задачу розпізнавання, яка є більш простою і тому може слугувати нижньою оцінкою складності.
Представлення у вигляді задачі розпізнавання запроваджує додатковий параметр P — бажана вартість предметів у рюкзаку та ставить запитання чи існує ще один варіант пакування, з сумарною вартістю запакованих предметів більшою за P. Мета запровадження задачі розпізнавання полягає в тому, що з точки зору теорії обчислювальної складності та NP-повноти для неї легше визначати складність. Якщо цільову функцію не складно обчислювати, то задача розпізнавання не складніша за відповідну задачу оптимізації. Таким чином, із NP-повноти задачі розпізнавання випливає NP-повнота задачі оптимізації.
Задача розпізнавання для оптимізаційної задачі 0-1 пакування рюкзака формулюється так: Задано скінченну множину U об'єктів, вагу , вартість для кожного об'єкта та цілі числа W (ємність рюкзака) та P (бажана вартість). Чи існує така підмножина , що:
- , та ?
Зв'язок з іншими задачами
Задача пакування рюкзака цікава з точки зору інформатики з багатьох причин:
- Задача пакування рюкзака у формі проблеми вибору (чи може бути досягнуто значення, щонайменше V, без перевищення ваги W?) є NP-повною, тому в загальному випадку не існує алгоритму як правильного, так і швидкого (який виконується за (поліноміальний час)).
- Хоча проблема вибору є NP-повною, проблема оптимізації є NP-складною, то вона, щонайменше, таке ж складна, як і проблема вибору, і тому не існує поліноміального алгоритму, який може визначити, чи є рішення оптимальним (це б означало, що не існує рішення, яке дає значення більше V, таким чином розв'язуючи NP-повну проблему вибору).
- Існує псевдополіноміальний алгоритм, який використовує динамічне програмування.
- Існує схема наближення до поліноміального часу, яка використовує наведений вище псевдополіноміальний алгоритм як підпрограму.
- У більшості випадків, що виникають на практиці, і для «випадкових екземплярів» з деяких ймовірнісних розподілів, все ж таки можуть бути розв'язані точно.
Наближені методи розв'язання
Як і для інших NP-повних задач, в деяких випадках достатньо знайти рішення, наближене до оптимального, але не обов'язково оптимальне. Бажано, також, щоб різниця між оптимальним розв'язком та знайденим була гарантованих розмірів.
Далі під ефективністю предмета розуміється відношення його вартості до ваги. Чим вище ефективність предмета, тим кориснішим він є для пакування.
Жадібний алгоритм
Одним з найпростіших алгоритмів пошуку приблизного розв'язку є жадібний алгоритм. Ідея алгоритму полягає в тому, щоб класти до рюкзака в першу чергу найефективніші предмети, аж до його заповнення:
впорядкувати предмети у порядку зменшення ефективності w_пак: = 0
для i від 1 до n якщо w[i] + w_пак <= W тоді x[i] := 1 w_пак := w_пак + w[i] інакше x[i] := 0 кінець якщо кінець для
Точні методи
Класична задача пакування рюкзака була вивчена досить глибоко. Існує багато методів пошуку точних розв'язків задачі. Більшість з них є покращеними варіантами одного з наведених нижче методів пошуку точного розв'язку задачі. А саме використовується підхід динамічне програмування, метод гілок і меж або [en] обох підходів.
Динамічне програмування
Задача пакування рюкзака має властивість суб-оптимальної структури, тобто, можна знайти оптимальний розв'язок задачі з змінними на основі розв'язку задачі з змінною. Ця властивість дозволяє застосувати засоби динамічного програмування для розв'язання задачі пакування рюкзака.
0-1 задача пакування рюкзака
Нехай потрібно розв'язати 0-1 задачу пакування рюкзака. Позначимо через KP(i, c) максимальну вартість, яку можна отримати для перших предметів із загальною вагою меншою або рівною c. Задача пакування рюкзака зводиться до знаходження KP(n, W).
Ідея полягає в тому, що оптимальний розв'язок задачі KP(i, c) можна отримати, використовуючи розв'язки двох простіших задач:
- задачі з змінними для рюкзака з такою ж ємністю c (KP(i−1, c)), та ;
- задачі з змінними для рюкзака з ємністю (), та .
Розв'язок задачі пакування рюкзака з 0 змінними (KP (0 ,*)) дорівнює нулю. Розв'язок задачі пакування рюкзака при c=0 (KP (* ,0)) також дорівнює нулю.
Тепер можна записати рекурсивно:
- , якщо (новий предмет важчий, ніж поточний резерв ваги)
- , якщо .
Потім будується таблиця 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, *].
Часова складність алгоритму дорівнює . Алгоритм має дві переваги:
- Швидкість;
- Не потрібне сортування змінних.
та недолік:
- вимагає порівняно багато пам'яті (що робить його не прийнятним для розв'язання великих задач).
Цей метод було розроблено та [en] в 1972 році.
Метод гілок і меж
Подібно до інших задач комбінаторної оптимізації, задача пакування рюкзака може бути розв'язана методом гілок і меж (англ. Branch-and-bound algorithm). Застосування методу гілок і меж до розв'язання задачі пакування рюкзака вперше запропонував Колесар в 1967 році. Варіант алгоритму розроблений Грінбергом та Хегерічем в 1970 році мав істотно нижчі вимоги до пам'яті та часу. Горовіц та Сані в 1974 році запропонували свій алгоритм побудований на основі попередніх варіантів. Цей алгоритм найефективніший та найпростіший для реалізації у порівнянні з попередніми алгоритмами. Запропонований Мартело та Тозом алгоритм набув значного поширення. Перевагою цього методу є низькі вимоги до обсягів необхідної пам'яті.
Примітки
- Mathews, G. B. (25 June 1897). (PDF). Proceedings of the London Mathematical Society. 28: 486—490. doi:10.1112/plms/s1-28.1.486. Архів оригіналу (PDF) за 26 травня 2012. Процитовано 26 липня 2019.
- Dantzig, Tobias. Numbers: The Language of Science, 1930.
- Richard M. Karp (1972). (PDF). У R. E. Miller; J. W. Thatcher; J.D. Bohlinger (ред.). Complexity of Computer Computations. New York: Plenum. с. 85—103. doi:10.1007/978-1-4684-2001-2_9. Архів оригіналу (PDF) за 10 лютого 2021. Процитовано 26 липня 2019.
- Skiena, S. S. (September 1999). Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository. ACM SIGACT News. 30 (3): 65—74. CiteSeerX 10.1.1.41.8357. doi:10.1145/333623.333627. ISSN 0163-5700.
- Kellerer, Pferschy, and Pisinger, 2004, с. 461.
- Kellerer, Pferschy, and Pisinger, 2004, с. 465.
- Kellerer, Pferschy, and Pisinger, 2004, с. 472.
- Silvano, 1990, с. 2.
- Бурков, Горгидзе, Ловецкий, 1974, с. 217.
- Kellerer, Pferschy, and Pisinger, 2004, с. 449.
- Feuerman, Martin; Weiss, Harvey (April 1973). A Mathematical Programming Model for Test Construction and Scoring. Management Science. 19 (8): 961—966. doi:10.1287/mnsc.19.8.961. JSTOR 2629127.
- Matthias Ehrgott (2005). Multicriteria Optimization. Springer. ISBN .
- (англ.) Michail G. Lagoudakis, The 0-1 Knapsack Problem — An Introductory Survey [ 2008-12-03 у Wayback Machine.], 1996.
- 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.
- Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). . European Journal of Operational Research. 123 (2): 168—181. CiteSeerX 10.1.1.41.2135. doi:10.1016/S0377-2217(99)00265-9. Архів оригіналу за 29 січня 2020. Процитовано 28 липня 2019.
- S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley and Sons, 1990
- Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization. 6 (1): 110—124. doi:10.1016/j.disopt.2008.09.004. ISSN 1572-5286.
- S. Martello, D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Manag. Sci., 45:414–424, 1999.
- Plateau, G.; Elkihel, M. (1985). A hybrid algorithm for the 0-1 knapsack problem. Methods of Oper. Res. 49: 277—293.
- Martello, S.; Toth, P. (1984). A mixture of dynamic programming and branch-and-bound for the subset-sum problem. Manag. Sci. 30 (6): 765—771. doi:10.1287/mnsc.30.6.765.
- (англ.) R. S. Garfinkel et G. L. Nemhauser. Integer Pogramming. John Wiley & Sons, New York, 1972. .
- (англ.) Silvano Martello et Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990 .
Література
- Hans Kellerer, Ulright Pferschy and David Pisinger, Knapsack Problems, Springer, 2004 . (англ.)
- Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163—166, 1985. (англ.)
Див. також
Посилання
- Динамічне програмування. 0-1 задача пакування рюкзака [ 16 лютого 2012 у Wayback Machine.] (слайди лекції) (англ.)
- Слайди лекції з динамічного програмування [ 19 квітня 2009 у Wayback Machine.] (п.4. Задача пакування рюкзака). (рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Zadacha pakuvannya ryukzaka angl Knapsack problem zadacha kombinatornoyi optimizaciyi dlya zadanoyi mnozhini predmetiv kozhen z yakih maye vagu i cinnist viznachiti yaku kilkist kozhnogo z predmetiv slid vzyati tak shob sumarna vaga ne perevishuvala zadanu a sumarna cinnist bula maksimalnoyu Zadacha bere svoyu nazvu vid dovoli vidomoyi situaciyi koli potribno napovniti ryukzak sho zdaten vitrimati deyaku maksimalnu masu predmetami kozhen z yakih maye vartist abo korisnist ta masu Neobhidno obrati ob yekti v takij sposib abi maksimizuvati sumarnu vartist abo korist ale ne perevishiti maksimalno pripustimu masu Priklad odnovimirnoyi zadachi z obmezhennyam pro pakuvannya ryukzaka Yak pidibrati korobki tak shob yihnya vartist bula maksimalnoyu a sumarna vaga ne bilshe 15 kg Rozv yazok Yaksho dostupna dostatnya kilkist ekzemplyariv kozhnoyi korobki to pakuyetsya tri zhovti korobki ta tri siri korobki yaksho nayavni lishe ti sho zobrazheni na malyunku to pakuyutsya vsi krim zelenoyi korobki Zadacha chasto vinikaye pri rozpodili resursiv koli nayavni finansovi obmezhennya i vivchayetsya v takih oblastyah yak kombinatorika informatika teoriya skladnosti kriptografiya prikladna matematika Opisannya zadachi dosit proste ale rozv yazannya skladne Vidomi algoritmi na praktici zdatni rozv yazati zadachi dosit velikih rozmiriv Odnak unikalne formulyuvannya zadachi a takozh toj fakt sho vona prisutnya yak pidzadacha u bilshih zagalnishih problemah robit yiyi vazhlivoyu dlya naukovih doslidzhen IstoriyaZadacha pro pakuvannya ryukzaku doslidzhuyetsya vzhe ponad stolittya Vidoma zgadka she 1897 roku v statti en Sama nazva zadacha pro pakuvannya ryukzaku vidsilaye do rannih robit matematika en 1884 1956 i stosuyetsya zvichajnoyi problemi pakuvannya najbilsh cinnih abo korisnih rechej bez perevantazhennya Intensivne doslidzhennya problemi pochalos z seredini HH stolittya i v 1972 roci bula vklyuchena Richardom Karpom angl Richard Karp do spisku 21 NP povnoyi zadachi ZastosuvannyaDoslidzhennya 1998 roku provedene repozitariyem algoritmiv 28 listopada 2009 u Wayback Machine universitetu Stoni Bruk pokazalo sho z 75 algoritmichnih zadach zadacha pakuvannya ryukzaka bula 19 yu za po populyarnistyu i 3 yu z najbilsh neobhidnih pislya takih zadach yak sufiksne derevo ta zadacha pro pakuvannya v yemnosti Zadachu pakuvannya ryukzaka vikoristovuyut dlya modelyuvannya riznih problem zokrema U sistemah pidtrimki upravlinnya portfelem dlya balansuvannya ta diversifikaciyi vibranih kapitalovkladen iz metoyu poshuku najkrashogo balansu mizh rizikami ta efektivnistyu vkladiv u rizni finansovi aktivi ta dlya sek yuritizaciyi aktiviv Generuvannya klyuchiv dlya kriptosistem Merkle Gellmana ta inshih en Takozh zadacha pakuvannya ryukzaka vinikaye u velikij kilkosti promislovih zadach U en tkanini stalevi listi tosho vibir optimalnoyi shemi rozkroyu materialiv z metoyu zmenshennya kilkosti vidhodiv Pri zavantazhenni chovna abo litaka vibir bagazhiv dlya optimalnogo zavantazhennya transportnogo zasobu Pri rozmishenni vantazhiv na skladi minimalnoyi ploshi Odnim iz pershih zastosuvan algoritmiv pakuvannya ryukzaka bula stvorennya ta ocinka testiv v yakih testovani osobi mali vibir na yaki pitannya voni budut vidpovidati Pri nevelikij kilkosti prikladiv ce dovoli prozorij proces Napriklad yaksho ispit mistit 12 zapitan kozhen z yakih na 10 baliv testovanij osobi potribno vidpovisti lishe na 10 zapitan dlya dosyagnennya maksimalno mozhlivoyi ocinki 100 baliv Prote yaksho testovi zavdannya dayut riznu kilkist baliv zrobiti vibir vzhe vazhche Fyuerman i Vajs zaproponuvali sistemu v yakij studentam dayut geterogennij test iz zagalnoyu kilkistyu 125 mozhlivih baliv Studentiv prosyat vidpovisti na vsi pitannya naskilki ce mozhlivo Z usih mozhlivih pidmnozhin zavdan zagalni znachennya yakih dorivnyuyut abo ne perevishuyut 100 algoritm viznachaye yakij pidnabir dast kozhnomu studentu najvishij mozhlivij bal Postanovka zadachiDiv takozh Spisok zadach pro napovnennya ryukzaka Zadachu pakuvannya ryukzaka mozhna viznachiti zasobami matematichnogo aparatu Nehaj kozhnomu ob yektovi dlya pakuvannya zistavleno indeks i yakij prijmaye znachennya vid 1 do n Chisla w i displaystyle w i ta p i displaystyle p i vidpovidayut vazi ta vartosti ob yekta i Maksimalna pripustima masa yaku zdaten vitrimati ryukzak dorivnyuye W 0 1 zadacha pakuvannya ryukzaka Isnuye bagato variantiv zapovnennya ryukzaka Dlya opisannya okremogo variantu pakuvannya neobhidno vkazati dlya kozhnogo ob yekta chi jogo obrano zapakovano Dlya cogo mozhna vikoristati dvijkovij vektor X x 1 x 2 x n displaystyle X x 1 x 2 dots x n komponenta x i displaystyle x i yakogo dorivnyuvatime 1 yaksho i tij ob yekt zapakovano ta 0 yaksho ni Cej vektor nazivayetsya vektorom zapovnennya Vagu ta vartist zapakovanih predmetiv mozhna obchisliti yak funkciyu vid vektora zapovnennya Dlya zadanogo vektora zapovnennya X vartist predmetiv zapakovanih u ryukzak dorivnyuye z X i x i 1 p i i 1 n x i p i displaystyle z X sum i x i 1 p i sum i 1 n x i p i Analogichno zagalna masa predmetiv dorivnyuye w X i 1 n x i w i displaystyle w X sum i 1 n x i w i Takim chinom zadacha pakuvannya ryukzaka polyagaye u vidshukanni takogo vektora zapovnennya X x 1 x 2 x n displaystyle X x 1 x 2 dots x n sho maksimizuye funkciyu z X displaystyle z X za umovi w X i 1 n x i w i W displaystyle w X sum i 1 n x i w i leqslant W 1 Tobto zagalna masa obranih predmetiv w X displaystyle w X ne perevishuye mozhlivosti ryukzaka W displaystyle W Vzagali diyut taki dodatkovi umovi i 1 n w i gt W displaystyle sum i 1 n w i gt W vsi dostupni ob yekti ne mozhlivo poklasti do ryukzaka razom p i gt 0 i 1 n displaystyle p i gt 0 forall i in 1 dots n bud yakij dodatkovij ob yekt nadaye perevagu w i gt 0 i 1 n displaystyle w i gt 0 forall i in 1 dots n bud yakij ob yekt vikoristovuye resursi Terminologiya Funkciya z X displaystyle z X nazivayetsya cilovoyu Bud yakij vektor X displaystyle X sho vidpovidaye umovi 1 nazivayetsya pripustimim Yaksho vartist z X displaystyle z X maksimalna to vektor X displaystyle X nazivayetsya optimalnim Pripustimo okrim vartosti predmeti mayut she odnu harakteristiku napriklad shilnist Zadacha poshuku vektora zapovnennya X displaystyle X sho maksimizuye obidvi funkciyi sumarna vartist ta sumarna shilnist ye bagatokriterialnim variantom 0 1 zadachi pakuvannya ryukzaka Obmezhena zadacha pakuvannya ryukzaka obmezhuye kilkist x i displaystyle x i kopij kozhnogo vidu predmeta maksimalnim cilim znachennyam k i displaystyle k i Matematichno cyu zadachu mozhna sformulyuvati tak maksimizuvati i 1 n p i x i displaystyle qquad sum i 1 n p i x i za umovi i 1 n w i x i W x i 0 1 k i displaystyle qquad sum i 1 n w i x i leqslant W quad quad x i in 0 1 ldots k i Neobmezhena zadacha pakuvannya ryukzaka NZPR ne nakladaye verhnoyi mezhi dlya kilkosti kopij kozhnogo vidu predmeta Tobto potribno maksimizuvati i 1 n p i x i displaystyle qquad sum i 1 n p i x i za umovi i 1 n w i x i W x i 0 1 displaystyle qquad sum i 1 n w i x i leqslant W quad quad x i in 0 1 ldots Priklad takoyi zadachi navedena na malyunku u vstupnij chastini div tekst Yaksho dostupna dostatnya kilkist ekzemplyariv kozhnoyi korobki Osoblivij interes predstavlyaye okremij vipadok zadachi pakuvannya ryukzaka z takimi vlastivostyami vona ye problemoyu viboru vona ye 0 1 zadacheyu dlya kozhnogo vidu predmeta vaga dorivnyuye vartosti w i p i displaystyle w i p i U comu razi zadacha ekvivalentna takij zadachi zadano mnozhinu nevid yemnih cilih chisel chi isnuye bud yaka yiyi pidmnozhina suma elementiv yakoyi skladaye tochno W Abo yaksho dopuskayetsya vid yemna vaga i W dorivnyuye nulyu to zadacheyu ye zadano mnozhinu cilih chisel chi isnuye neporozhnya pidmnozhina suma elementiv yakoyi tochno dorivnyuye 0 Cej okremij vipadok nazivayetsya zadacheyu sumi pidmnozhini U galuzi kriptografiyi termin zadacha pakuvannya ryukzaka chasto vikoristovuyetsya dlya poznachennya konkretno zadachi sumi pidmnozhini Yaksho dopuskayetsya dekilka ryukzakiv to zadachu krashe rozglyadati yak zadachu pakuvannya v yemnosti Formulyuvannya u terminah teoriyi mnozhin Zadachu pakuvannya ryukzaka mozhna opisati terminami teoriyi mnozhin Nehaj zadano mnozhinu ob yektiv U displaystyle U vagu w u Z displaystyle w u in Z ta vartist z u Z displaystyle z u in Z dlya kozhnogo ob yekta u U displaystyle u in U ta maksimalnu pripustimu vagu W displaystyle W Neobhidno znajti pidmnozhinu U displaystyle U taku shob u U w u W displaystyle sum u in U w u leqslant W ta u U p u m a x displaystyle sum u in U p u max Obchislyuvalna skladnistDiv takozh NP skladna zadacha ta NP povna zadacha Zadacha rozpiznavannya Dlya ocinki algoritmichnoyi skladnosti zadachi yiyi optimizacijne formulyuvannya zminyuyut na zadachu rozpiznavannya yaka ye bilsh prostoyu i tomu mozhe sluguvati nizhnoyu ocinkoyu skladnosti Predstavlennya u viglyadi zadachi rozpiznavannya zaprovadzhuye dodatkovij parametr P bazhana vartist predmetiv u ryukzaku ta stavit zapitannya chi isnuye she odin variant pakuvannya z sumarnoyu vartistyu zapakovanih predmetiv bilshoyu za P Meta zaprovadzhennya zadachi rozpiznavannya polyagaye v tomu sho z tochki zoru teoriyi obchislyuvalnoyi skladnosti ta NP povnoti dlya neyi legshe viznachati skladnist Yaksho cilovu funkciyu ne skladno obchislyuvati to zadacha rozpiznavannya ne skladnisha za vidpovidnu zadachu optimizaciyi Takim chinom iz NP povnoti zadachi rozpiznavannya viplivaye NP povnota zadachi optimizaciyi Zadacha rozpiznavannya dlya optimizacijnoyi zadachi 0 1 pakuvannya ryukzaka formulyuyetsya tak Zadano skinchennu mnozhinu U ob yektiv vagu w u Z displaystyle w u in Z vartist z u Z displaystyle z u in Z dlya kozhnogo ob yekta u U displaystyle u in U ta cili chisla W yemnist ryukzaka ta P bazhana vartist Chi isnuye taka pidmnozhina U displaystyle U sho u U w u W displaystyle sum u in U w u leq W ta u U z u P displaystyle sum u in U z u geq P Zv yazok z inshimi zadachami Zadacha pakuvannya ryukzaka cikava z tochki zoru informatiki z bagatoh prichin Zadacha pakuvannya ryukzaka u formi problemi viboru chi mozhe buti dosyagnuto znachennya shonajmenshe V bez perevishennya vagi W ye NP povnoyu tomu v zagalnomu vipadku ne isnuye algoritmu yak pravilnogo tak i shvidkogo yakij vikonuyetsya za polinomialnij chas Hocha problema viboru ye NP povnoyu problema optimizaciyi ye NP skladnoyu to vona shonajmenshe take zh skladna yak i problema viboru i tomu ne isnuye polinomialnogo algoritmu yakij mozhe viznachiti chi ye rishennya optimalnim ce b oznachalo sho ne isnuye rishennya yake daye znachennya bilshe V takim chinom rozv yazuyuchi NP povnu problemu viboru Isnuye psevdopolinomialnij algoritm yakij vikoristovuye dinamichne programuvannya Isnuye shema nablizhennya do polinomialnogo chasu yaka vikoristovuye navedenij vishe psevdopolinomialnij algoritm yak pidprogramu U bilshosti vipadkiv sho vinikayut na praktici i dlya vipadkovih ekzemplyariv z deyakih jmovirnisnih rozpodiliv vse zh taki mozhut buti rozv yazani tochno Nablizheni metodi rozv yazannyaYak i dlya inshih NP povnih zadach v deyakih vipadkah dostatno znajti rishennya nablizhene do optimalnogo ale ne obov yazkovo optimalne Bazhano takozh shob riznicya mizh optimalnim rozv yazkom ta znajdenim bula garantovanih rozmiriv Dali pid efektivnistyu predmeta rozumiyetsya vidnoshennya jogo vartosti do vagi Chim vishe efektivnist predmeta tim korisnishim vin ye dlya pakuvannya Zhadibnij algoritm Dvi fazi zhadibnogo algoritmu Livoruch vporyadkuvannya predmetiv za yihnoyu efektivnistyu v comu razi vartist na kilo vagi Pravoruch pakuvannya v ryukzak yaksho ye mozhlivist Otrimanij rozv yazok daye 11 ta 11 kg v toj chas yak optimalnij 12 ta 14 kg Odnim z najprostishih algoritmiv poshuku pribliznogo rozv yazku ye zhadibnij algoritm Ideya algoritmu polyagaye v tomu shob klasti do ryukzaka v pershu chergu najefektivnishi predmeti azh do jogo zapovnennya vporyadkuvati predmeti u poryadku zmenshennya efektivnosti w pak 0 dlya i vid 1 do n yaksho w i w pak lt W todi x i 1 w pak w pak w i inakshe x i 0 kinec yaksho kinec dlyaTochni metodiKlasichna zadacha pakuvannya ryukzaka bula vivchena dosit gliboko Isnuye bagato metodiv poshuku tochnih rozv yazkiv zadachi Bilshist z nih ye pokrashenimi variantami odnogo z navedenih nizhche metodiv poshuku tochnogo rozv yazku zadachi A same vikoristovuyetsya pidhid dinamichne programuvannya metod gilok i mezh abo en oboh pidhodiv Dinamichne programuvannya Dokladnishe Dinamichne programuvannya Zadacha pakuvannya ryukzaka maye vlastivist sub optimalnoyi strukturi tobto mozhna znajti optimalnij rozv yazok zadachi z i displaystyle i zminnimi na osnovi rozv yazku zadachi z i 1 displaystyle i 1 zminnoyu Cya vlastivist dozvolyaye zastosuvati zasobi dinamichnogo programuvannya dlya rozv yazannya zadachi pakuvannya ryukzaka 0 1 zadacha pakuvannya ryukzaka Nehaj potribno rozv yazati 0 1 zadachu pakuvannya ryukzaka Poznachimo cherez KP i c maksimalnu vartist yaku mozhna otrimati dlya pershih i displaystyle i predmetiv iz zagalnoyu vagoyu menshoyu abo rivnoyu c Zadacha pakuvannya ryukzaka zvoditsya do znahodzhennya KP n W Ideya polyagaye v tomu sho optimalnij rozv yazok zadachi KP i c mozhna otrimati vikoristovuyuchi rozv yazki dvoh prostishih zadach zadachi z i 1 displaystyle i 1 zminnimi dlya ryukzaka z takoyu zh yemnistyu c KP i 1 c ta x i 0 displaystyle x i 0 zadachi z i 1 displaystyle i 1 zminnimi dlya ryukzaka z yemnistyu c w i displaystyle c w i K P i 1 c w i displaystyle KP i 1 c w i ta x i 1 displaystyle x i 1 Rozv yazok zadachi pakuvannya ryukzaka z 0 zminnimi KP 0 dorivnyuye nulyu Rozv yazok zadachi pakuvannya ryukzaka pri c 0 KP 0 takozh dorivnyuye nulyu Teper mozhna zapisati K P i c displaystyle KP i c rekursivno K P 0 c 0 0 c W displaystyle KP 0 c 0 quad 0 leq c leq W K P i 0 0 0 i n displaystyle KP i 0 0 quad 0 leq i leq n K P i c K P i 1 c displaystyle KP i c KP i 1 c yaksho w i gt c displaystyle w i gt c novij predmet vazhchij nizh potochnij rezerv vagi K P i c max K P i 1 c K P i 1 c w i p i displaystyle KP i c max KP i 1 c KP i 1 c w i p i yaksho w i c displaystyle w i leqslant c Potim buduyetsya tablicya T i c elementi yakoyi mistyat znachennya rozv yazkiv zadach KP i c v nastupnij sposib dlya c vid 0 do W robiti T 0 c 0 kinec dlya dlya i vid 1 do n robiti dlya c vid 0 do W robiti yaksho c gt w i to T i c max T i 1 c T i 1 c w i p i inakshe T i c T i 1 c kinec yaksho kinec dlya kinec dlya vivesti T n W Koli tablicya pobudovana vipadok zadachi T n W slid zvesti do vipadku T 0 Chasova skladnist algoritmu dorivnyuye O n W displaystyle O nW Algoritm maye dvi perevagi Shvidkist Ne potribne sortuvannya zminnih ta nedolik vimagaye porivnyano bagato pam yati sho robit jogo ne prijnyatnim dlya rozv yazannya velikih zadach Cej metod bulo rozrobleno ta en v 1972 roci Metod gilok i mezh Podibno do inshih zadach kombinatornoyi optimizaciyi zadacha pakuvannya ryukzaka mozhe buti rozv yazana metodom gilok i mezh angl Branch and bound algorithm Zastosuvannya metodu gilok i mezh do rozv yazannya zadachi pakuvannya ryukzaka vpershe zaproponuvav Kolesar v 1967 roci Variant algoritmu rozroblenij Grinbergom ta Hegerichem v 1970 roci mav istotno nizhchi vimogi do pam yati ta chasu Gorovic ta Sani v 1974 roci zaproponuvali svij algoritm pobudovanij na osnovi poperednih variantiv Cej algoritm najefektivnishij ta najprostishij dlya realizaciyi u porivnyanni z poperednimi algoritmami Zaproponovanij Martelo ta Tozom algoritm nabuv znachnogo poshirennya Perevagoyu cogo metodu ye nizki vimogi do obsyagiv neobhidnoyi pam yati PrimitkiMathews G B 25 June 1897 PDF Proceedings of the London Mathematical Society 28 486 490 doi 10 1112 plms s1 28 1 486 Arhiv originalu PDF za 26 travnya 2012 Procitovano 26 lipnya 2019 Dantzig Tobias Numbers The Language of Science 1930 Richard M Karp 1972 PDF U R E Miller J W Thatcher J D Bohlinger red Complexity of Computer Computations New York Plenum s 85 103 doi 10 1007 978 1 4684 2001 2 9 Arhiv originalu PDF za 10 lyutogo 2021 Procitovano 26 lipnya 2019 Skiena S S September 1999 Who is Interested in Algorithms and Why Lessons from the Stony Brook Algorithm Repository ACM SIGACT News 30 3 65 74 CiteSeerX 10 1 1 41 8357 doi 10 1145 333623 333627 ISSN 0163 5700 Kellerer Pferschy and Pisinger 2004 s 461 Kellerer Pferschy and Pisinger 2004 s 465 Kellerer Pferschy and Pisinger 2004 s 472 Silvano 1990 s 2 Burkov Gorgidze Loveckij 1974 s 217 Kellerer Pferschy and Pisinger 2004 s 449 Feuerman Martin Weiss Harvey April 1973 A Mathematical Programming Model for Test Construction and Scoring Management Science 19 8 961 966 doi 10 1287 mnsc 19 8 961 JSTOR 2629127 Matthias Ehrgott 2005 Multicriteria Optimization Springer ISBN 3 540 21398 8 angl Michail G Lagoudakis The 0 1 Knapsack Problem An Introductory Survey 2008 12 03 u Wayback Machine 1996 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 Andonov Rumen Poirriez Vincent Rajopadhye Sanjay 2000 European Journal of Operational Research 123 2 168 181 CiteSeerX 10 1 1 41 2135 doi 10 1016 S0377 2217 99 00265 9 Arhiv originalu za 29 sichnya 2020 Procitovano 28 lipnya 2019 S Martello P Toth Knapsack Problems Algorithms and Computer Implementations John Wiley and Sons 1990 Poirriez Vincent Yanev Nicola Andonov Rumen 2009 A hybrid algorithm for the unbounded knapsack problem Discrete Optimization 6 1 110 124 doi 10 1016 j disopt 2008 09 004 ISSN 1572 5286 S Martello D Pisinger P Toth Dynamic programming and strong bounds for the 0 1 knapsack problem Manag Sci 45 414 424 1999 Plateau G Elkihel M 1985 A hybrid algorithm for the 0 1 knapsack problem Methods of Oper Res 49 277 293 Martello S Toth P 1984 A mixture of dynamic programming and branch and bound for the subset sum problem Manag Sci 30 6 765 771 doi 10 1287 mnsc 30 6 765 angl R S Garfinkel et G L Nemhauser Integer Pogramming John Wiley amp Sons New York 1972 ISBN 0 471 29195 1 angl Silvano Martello et Paolo Toth Knapsack Problems Algorithms and Computer Implementations John Wiley amp Sons 1990 ISBN 0 471 92420 2 LiteraturaHans Kellerer Ulright Pferschy and David Pisinger Knapsack Problems Springer 2004 ISBN 3 540 40286 1 angl Honsberger R Mathematical Gems III Washington DC Math Assoc Amer pp 163 166 1985 angl Div takozhPortal Matematika Spisok zadach pro napovnennya ryukzaka 21 NP povna zadacha Karpa Kombinatorna optimizaciya Zadacha pro pakuvannya v yemnosti Zadacha komivoyazheraPosilannyaDinamichne programuvannya 0 1 zadacha pakuvannya ryukzaka 16 lyutogo 2012 u Wayback Machine slajdi lekciyi angl Slajdi lekciyi z dinamichnogo programuvannya 19 kvitnya 2009 u Wayback Machine p 4 Zadacha pakuvannya ryukzaka ros