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

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

Общим для всех видов является наличие набора из $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_ix_i$

при наличии ограничения $\sum_{i=1}^n p_ix_i \le P$ на вместимость рюкзака^[1][2].

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

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

максимизировать $\sum_{i=1}^n c_ix_i$

так чтобы $\sum_{i=1}^n p_ix_i \le P$ выполнялось условие на вместимость

и $x_i \in (0,1,...,m_i)$ для всех $i= 1,2,...,n$^[3].

Число $m_i$ называют границей^[3].

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

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

максимизировать $\sum_{i=1}^n c_ix_i$

так чтобы $\sum_{i=1}^n p_ix_i \le P$ выполнялось условие на вместимость

и целое $x_i \ge 0$ для всех $i= 1,2,...,n$^[4].

Рюкзак с мультивыбором(англ. 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} \le P$ выполнялось условие на вместимость,

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

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

Пусть у нас есть $n$ предметов и $m$ рюкзаков ($m\le 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_{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$^[5].

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

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

максимизировать $\sum_{i=1}^n c_ix_i$

так чтобы $\sum_{i=1}^n p_{ij}x_i \le P_j$, $j= 1,2,...,m$

и $x_i \ge 0$ для всех $i= 1,2,...,n$^[4].

Примечания

1. ↑ Бурков, 1974, p. 217
2. ↑ Silvano, 1990, p. 2
3. ↑ ^{1 2} Pisinger, 1995, p. 127
4. ↑ ^{1 2} Pisinger, 1995, p. 147
5. ↑ Silvano, 1990, p. 157

Литература

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

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

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

1. Silvano Martelo, Paolo Toth Knapsack problems. — Wiley, 1990. — 306 с.
2. David Pisinger Knapsack problems. — 1995.