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

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

Рюкзак 0-1 (Шаблон:Lang-en)

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

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

Обмежений рюкзак (Шаблон:Lang-en)

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

так, щоб$\sum _{i=1}^n{p}_i{x}_i\le P$ виконалась умова на місткість

і $x_i\in (0,1,...,m_i)$ для всіх $i=1,2,...,n$.

Число $m_i$ називають границею, межею.

Необмежений рюкзак (цілочисельний рюкзак) (Шаблон:Lang-en)

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

так щоб $\sum _{i=1}^n{p}_i{x}_i\le P$ виконалась умова на місткість

і ціле $x_i\ge 0$ для всіх $i=1,2,...,n$.

Рюкзак з мультивибором (Шаблон:Lang-en)

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

так щоб $\sum _{i=1}^n\sum _{j\in S_i}{p}_{ij}{x}_{ij}\le P$ виконувалась умова на місткість,

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

Мультиплікативний рюкзак (Шаблон:Lang-en)

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

так щоб $\sum _{i=1}^n{p}_j{x}_{ij}\le P_i$ виконувалась умова для всіх $i=1,2,...,n$,

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

Багатовимірний рюкзак (Шаблон:Lang-en)

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

так щоб $\sum _{i=1}^n{p}_{ij}{x}_i\le P_j,j=1,2,...,m$

и $x_i\ge 0$ для всіх $i=1,2,...,n$.

Література

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