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

Задача о рюкзаке (или ранце) — это одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Поэтому у задачи существует несколько разновидностей.

Общим для всех видов является наличие набора из $n$ предметов, с двумя параметрами — вес $p_{i}>0$ и ценность $c_{i}>0$$,i=1,2,...,n$.Есть рюкзак, определенной вместимости $P$. Задача — собрать рюкзак с максимальной ценностью предметов внутри, соблюдая при этом весовое ограничение рюкзака. Обычно все параметры — целые, не отрицательные числа.

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

Это самая распространенная разновидность рюкзака. Пусть $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}\leq P$ на вместимость рюкзака.

Ограниченный рюкзак (англ. Bounded Knapsack Problem)

Каждый предмет $x_{i}$ может быть выбран ограниченное число раз. Задача:

максимизировать $\sum _{i=1}^{n}c_{i}x_{i}$

так, чтобы $\sum _{i=1}^{n}p_{i}x_{i}\leq P$ выполнялось условие на вместимость

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

Число $m_{i}$ называют границей.

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

Каждый предмет $x_{i}$ может быть выбран неограниченное число раз. Задача:

максимизировать $\sum _{i=1}^{n}c_{i}x_{i}$

так, чтобы $\sum _{i=1}^{n}p_{i}x_{i}\leq P$ выполнялось условие на вместимость

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

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

Все предметы $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}\leq P$ выполнялось условие на вместимость,

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

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

Пусть у нас есть $n$ предметов и $m$ рюкзаков ($m\leq n$). У каждого предмета, как и раньше, есть вес $p_{j}>0$ и ценность $c_{j}>0$$j=1,2,...,n$, у каждого рюкзака соответственно своя вместимость $P_{i}$ при $i=1,2,...,m$. $x_{i}\in {0,1}$. Задача:

максимизировать $\sum _{i=1}^{m}\sum _{j=1}^{n}c_{j}x_{ij}$

так, чтобы $\sum _{i=1}^{n}p_{j}x_{ij}\leq P_{i}$ выполнялось условие для всех $i=1,2,...,m$,

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

Многомерный рюкзак (англ. Multi-dimensional knapsack problem)

Если есть более одного ограничения на рюкзак, например объем и вес, задачу называют m-мерной задачей о ранце. Например, для не ограниченного варианта:

максимизировать $\sum _{i=1}^{n}c_{i}x_{i}$

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

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

Квадратичная задача о рюкзаке (англ. Quadratic knapsack problem)

Квадратичная задача о ранце представляет собой модификацию классических задач о ранце с ценностью, являющейся квадратичной формой. Пусть $x=(x_{1},..,x_{n})$ - вектор, задающий, сколько экземпляров каждого предмета окажется в рюкзаке. Задача:

максимизировать $x^{T}Qx$

при условиях $\sum _{i=1}^{n}p_{i}x_{i}\leq P$, $x\in B^{n}$, или

минимизировать $x^{T}Qx$

при условиях $\sum _{i=1}^{n}p_{i}x_{i}\geq P$, $x\in B^{n}$.

При этом $Q$ — неотрицательно определенная матрица размера $n\times n$, $B^{n}$ задаёт ограничения на количество предметов.

Литература

на русском языке

1. В. Н. Бурков, И. А. Горгидзе, С. Е. Ловецкий. Прикладные задачи теории графов. — М., 1974. — 232 с.

на английском языке

1. Silvano Martelo, Paolo Toth. Knapsack problems. — Wiley, 1990. — 306 с.
2. David Pisinger. Knapsack problems. — 1995. Архивная копия от 22 декабря 2012 на Wayback Machine

Ссылки

1. Алгоритм рюкзака