Список задач про наповнення рюкзака

Задача про наповнення рюкзака — це одна з задач комбінаторної оптимізації. Задача отримала назву від максимізаційної задачі пакування якомога більшої кількості речей в рюкзак при умові, щоб загальний об'єм (чи вага) всіх предметів, здатних поміститись в рюкзак, обмежений. Тому в цієї задачі існує декілька підвидів. Загальним для всіх видів є наявність набору з n предметів, кожен з двома параметрами — вага ${\displaystyle P_{i}>0}$ і ціна ${\displaystyle C_{i}>0}$, ${\displaystyle i=1,2,...,n}$.Є рюкзак, визначеної місткості ${\displaystyle P}$. Завдання — зібрати рюкзак з максимальною цінністю предметів всередині, зберігаючи при цьому вагове обмеження рюкзака. Зазвичай всі параметри є цілими невід'ємними числами.

Рюкзак 0-1 (англ. 0-1 Knapsack Problem)

Це найбільш поширений різновид рюкзака. Нехай ${\displaystyle X_{i}}$ приймає два значення: ${\displaystyle X_{i}=1}$, якщо вантаж запакований, і ${\displaystyle X_{i}=0}$ в іншому випадку, де ${\displaystyle i=1,2,...,n}$. Завдання: Максимізувати ${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$

при наявності обмеження ${\displaystyle \sum _{i=1}^{n}p_{i}x_{i}\leq P}$ на місткість рюкзака.

Обмежений рюкзак (англ. Bounded Knapsack Problem)

Кожен предмет ${\displaystyle X_{i}}$ може бути обраний обмежену кількість раз. Завдання: Максимізувати ${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$

так, щоб${\displaystyle \sum _{i=1}^{n}p_{i}x_{i}\leq P}$ виконалась умова на місткість

і ${\displaystyle x_{i}\in (0,1,...,m_{i})}$ для всіх ${\displaystyle i=1,2,...,n}$.

Число ${\displaystyle m_{i}}$ називають границею, межею.

Необмежений рюкзак (цілочисельний рюкзак) (англ. Unbounded Knapsack Problem (integer knapsack))

Кожен предмет ${\displaystyle x_{i}}$ може бути обраний необмежену кількість раз. Завдання: максимізувати ${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$

так щоб ${\displaystyle \sum _{i=1}^{n}p_{i}x_{i}\leq P}$ виконалась умова на місткість

і ціле ${\displaystyle x_{i}\geq 0}$ для всіх ${\displaystyle i=1,2,...,n}$.

Рюкзак з мультивибором (англ. Multiple-choice Knapsack Problem)

Всі предмети ${\displaystyle x_{i}}$ розділяють на ${\displaystyle s}$ класів ${\displaystyle S_{i}}$. Обов'язковою є умова вибору предмета з кожного класу. ${\displaystyle x_{i}}$ приймає значення тільки 0 і 1. Завдання: максимізувати ${\displaystyle \sum _{i=1}^{n}\sum _{j\in S_{i}}c_{ij}x_{ij}}$

так щоб ${\displaystyle \sum _{i=1}^{n}\sum _{j\in S_{i}}p_{ij}x_{ij}\leq P}$ виконувалась умова на місткість,

${\displaystyle \sum _{j\in S_{i}}x_{ij}=1}$ для всіх ${\displaystyle i=1,2,...,n}$

Мультиплікативний рюкзак (англ. Multiple Knapsack Problem)

Нехай в нас є ${\displaystyle n}$ предметів та ${\displaystyle m}$ рюкзаків ${\displaystyle (m\leq n)}$. У кожного предмета, як і раніше, є вага ${\displaystyle p_{j}=0}$ і ціна ${\displaystyle c_{j}=0j=1,2,...,n}$, у кожного рюкзака відповідно своя місткість ${\displaystyle P_{i}i=1,2,...,m.x_{i}\in {0,1}}$ Завдання: максимізувати ${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}}$

так щоб ${\displaystyle \sum _{i=1}^{n}p_{j}x_{ij}\leq P_{i}}$ виконувалась умова для всіх ${\displaystyle i=1,2,...,n}$,

${\displaystyle \sum _{j=1}^{m}x_{ij}=1}$ для всіх ${\displaystyle i=1,2,...,n}$.

Багатовимірний рюкзак (англ. Multy-dimensional knapsack problem)

Якщо є більше одного обмеження на рюкзак, наприклад об'єм і вага, задачу називають m-вимірною задачею про рюкзак. Наприклад, для необмеженого варіанта: максимізувати ${\displaystyle \sum _{i=1}^{n}c_{i}x_{i}}$

так щоб ${\displaystyle \sum _{i=1}^{n}p_{ij}x_{i}\leq P_{j},j=1,2,...,m}$

и ${\displaystyle x_{i}\geq 0}$ для всіх ${\displaystyle i=1,2,...,n}$.

Література

1. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с. (рос.)
2. Silvano Martelo, Paolo Toth Knapsack problems. — Wiley, 1990. — 306 с. (англ.)
3. David Pisinger Knapsack problems. — 1995. (англ.)