Було запропоновано цю статтю або розділ з Задача пакування рюкзака, але, можливо, це варто додатково . Пропозиція з грудня 2014. |
Задача про наповнення рюкзака — це одна з задач комбінаторної оптимізації. Задача отримала назву від максимізаційної задачі пакування якомога більшої кількості речей в рюкзак при умові, щоб загальний об'єм (чи вага) всіх предметів, здатних поміститись в рюкзак, обмежений. Тому в цієї задачі існує декілька підвидів. Загальним для всіх видів є наявність набору з n предметів, кожен з двома параметрами — вага і ціна , .Є рюкзак, визначеної місткості . Завдання — зібрати рюкзак з максимальною цінністю предметів всередині, зберігаючи при цьому вагове обмеження рюкзака. Зазвичай всі параметри є цілими невід'ємними числами.
Рюкзак 0-1 (англ. 0-1 Knapsack Problem)
Це найбільш поширений різновид рюкзака. Нехай приймає два значення: , якщо вантаж запакований, і в іншому випадку, де . Завдання: Максимізувати
при наявності обмеження на місткість рюкзака.
Обмежений рюкзак (англ. Bounded Knapsack Problem)
Кожен предмет може бути обраний обмежену кількість раз. Завдання: Максимізувати
так, щоб виконалась умова на місткість
і для всіх .
Число називають границею, межею.
Необмежений рюкзак (цілочисельний рюкзак) (англ. Unbounded Knapsack Problem (integer knapsack))
Кожен предмет може бути обраний необмежену кількість раз. Завдання: максимізувати
так щоб виконалась умова на місткість
і ціле для всіх .
Рюкзак з мультивибором (англ. Multiple-choice Knapsack Problem)
Всі предмети розділяють на класів . Обов'язковою є умова вибору предмета з кожного класу. приймає значення тільки 0 і 1. Завдання: максимізувати
так щоб виконувалась умова на місткість,
для всіх
Мультиплікативний рюкзак (англ. Multiple Knapsack Problem)
Нехай в нас є предметів та рюкзаків . У кожного предмета, як і раніше, є вага і ціна , у кожного рюкзака відповідно своя місткість Завдання: максимізувати
так щоб виконувалась умова для всіх ,
для всіх .
Багатовимірний рюкзак (англ. Multy-dimensional knapsack problem)
Якщо є більше одного обмеження на рюкзак, наприклад об'єм і вага, задачу називають m-вимірною задачею про рюкзак. Наприклад, для необмеженого варіанта: максимізувати
так щоб
и для всіх .
Література
- В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с. (рос.)
- Silvano Martelo, Paolo Toth Knapsack problems. — Wiley, 1990. — 306 с. (англ.)
- David Pisinger Knapsack problems. — 1995. (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Bulo zaproponovano ob yednati cyu stattyu abo rozdil z Zadacha pakuvannya ryukzaka ale mozhlivo ce varto dodatkovo Propoziciya z grudnya 2014 Zadacha pro napovnennya ryukzaka ce odna z zadach kombinatornoyi optimizaciyi Zadacha otrimala nazvu vid maksimizacijnoyi zadachi pakuvannya yakomoga bilshoyi kilkosti rechej v ryukzak pri umovi shob zagalnij ob yem chi vaga vsih predmetiv zdatnih pomistitis v ryukzak obmezhenij Tomu v ciyeyi zadachi isnuye dekilka pidvidiv Zagalnim dlya vsih vidiv ye nayavnist naboru z n predmetiv kozhen z dvoma parametrami vaga P i gt 0 displaystyle P i gt 0 i cina C i gt 0 displaystyle C i gt 0 i 1 2 n displaystyle i 1 2 n Ye ryukzak viznachenoyi mistkosti P displaystyle P Zavdannya zibrati ryukzak z maksimalnoyu cinnistyu predmetiv vseredini zberigayuchi pri comu vagove obmezhennya ryukzaka Zazvichaj vsi parametri ye cilimi nevid yemnimi chislami Ryukzak 0 1 angl 0 1 Knapsack Problem Ce najbilsh poshirenij riznovid ryukzaka Nehaj X i displaystyle X i prijmaye dva znachennya X i 1 displaystyle X i 1 yaksho vantazh zapakovanij i X i 0 displaystyle X i 0 v inshomu vipadku de i 1 2 n displaystyle i 1 2 n Zavdannya Maksimizuvati i 1 n c i x i displaystyle sum i 1 n c i x i pri nayavnosti obmezhennya i 1 n p i x i P displaystyle sum i 1 n p i x i leq P na mistkist ryukzaka Obmezhenij ryukzak angl Bounded Knapsack Problem Kozhen predmet X i displaystyle X i mozhe buti obranij obmezhenu kilkist raz Zavdannya Maksimizuvati i 1 n c i x i displaystyle sum i 1 n c i x i tak shob i 1 n p i x i P displaystyle sum i 1 n p i x i leq P vikonalas umova na mistkist i x i 0 1 m i displaystyle x i in 0 1 m i dlya vsih i 1 2 n displaystyle i 1 2 n Chislo m i displaystyle m i nazivayut graniceyu mezheyu Neobmezhenij ryukzak cilochiselnij ryukzak angl Unbounded Knapsack Problem integer knapsack Kozhen predmet x i displaystyle x i mozhe buti obranij neobmezhenu kilkist raz Zavdannya maksimizuvati i 1 n c i x i displaystyle sum i 1 n c i x i tak shob i 1 n p i x i P displaystyle sum i 1 n p i x i leq P vikonalas umova na mistkist i cile x i 0 displaystyle x i geq 0 dlya vsih i 1 2 n displaystyle i 1 2 n Ryukzak z multiviborom angl Multiple choice Knapsack Problem Vsi predmeti x i displaystyle x i rozdilyayut na s displaystyle s klasiv S i displaystyle S i Obov yazkovoyu ye umova viboru predmeta z kozhnogo klasu x i displaystyle x i prijmaye znachennya tilki 0 i 1 Zavdannya maksimizuvati i 1 n j S i c i j x i j displaystyle sum i 1 n sum j in S i c ij x ij tak shob i 1 n j S i p i j x i j P displaystyle sum i 1 n sum j in S i p ij x ij leq P vikonuvalas umova na mistkist j S i x i j 1 displaystyle sum j in S i x ij 1 dlya vsih i 1 2 n displaystyle i 1 2 n Multiplikativnij ryukzak angl Multiple Knapsack Problem Nehaj v nas ye n displaystyle n predmetiv ta m displaystyle m ryukzakiv m n displaystyle m leq n U kozhnogo predmeta yak i ranishe ye vaga p j 0 displaystyle p j 0 i cina c j 0 j 1 2 n displaystyle c j 0j 1 2 n u kozhnogo ryukzaka vidpovidno svoya mistkist P i i 1 2 m x i 0 1 displaystyle P i i 1 2 m x i in 0 1 Zavdannya maksimizuvati i 1 m j 1 n c i j x i j displaystyle sum i 1 m sum j 1 n c ij x ij tak shob i 1 n p j x i j P i displaystyle sum i 1 n p j x ij leq P i vikonuvalas umova dlya vsih i 1 2 n displaystyle i 1 2 n j 1 m x i j 1 displaystyle sum j 1 m x ij 1 dlya vsih i 1 2 n displaystyle i 1 2 n Bagatovimirnij ryukzak angl Multy dimensional knapsack problem Yaksho ye bilshe odnogo obmezhennya na ryukzak napriklad ob yem i vaga zadachu nazivayut m vimirnoyu zadacheyu pro ryukzak Napriklad dlya neobmezhenogo varianta maksimizuvati i 1 n c i x i displaystyle sum i 1 n c i x i tak shob i 1 n p i j x i P j j 1 2 m displaystyle sum i 1 n p ij x i leq P j j 1 2 m i x i 0 displaystyle x i geq 0 dlya vsih i 1 2 n displaystyle i 1 2 n LiteraturaV N Burkov I A Gorgidze S E Loveckij Prikladnye zadachi teorii grafov M 1974 232 s ros Silvano Martelo Paolo Toth Knapsack problems Wiley 1990 306 s angl David Pisinger Knapsack problems 1995 angl