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

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

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

Рюкзак 0-1 (англ. 0-1 Knapsack Problem)Править

Это самая распространенная разновидность рюкзака. Пусть $x_i$$x_i$  принимает два значения: $x_i=1$$x_i= 1$ , если груз упакован, и $x_i=0$$x_i= 0$  в противном случае, где $i=1,2,...,n$$i= 1,2,...,n$ . Задача:

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_i{x}_i$$\sum_{i=1}^n c_ix_i$ 

при наличии ограничения $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i{x}_i\le <!--\; \le \; -->P$$\sum_{i=1}^n p_ix_i \le P$  на вместимость рюкзака.

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

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

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_i{x}_i$$\sum_{i=1}^n c_ix_i$ 

так, чтобы $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i{x}_i\le <!--\; \le \; -->P$$\sum_{i=1}^n p_ix_i \le P$  выполнялось условие на вместимость

и $x_i\in <!--\; \in \; -->(0,1,...,m_i)$$x_i \in (0,1,...,m_i)$  для всех $i=1,2,...,n$$i= 1,2,...,n$ .

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

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

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

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_i{x}_i$$\sum_{i=1}^n c_ix_i$ 

так, чтобы $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i{x}_i\le <!--\; \le \; -->P$$\sum_{i=1}^n p_ix_i \le P$  выполнялось условие на вместимость

и целое $x_i\ge <!--\; \ge \; -->0$$x_i \ge 0$  для всех $i=1,2,...,n$$i= 1,2,...,n$ .

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

Все предметы $x_i$$x_i$  разделяют на $s$$s$  классов $S_i$$S_{i}$ . Обязательным является условие выбора только одного предмета из каждого класса. $x_i$$x_{i}$  принимает значение только 0 и 1. Задача:

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\underset{j\in <!--\; \in \; -->S_i}{\sum <!--\; \sum \; -->}{c}_{ij}{x}_{ij}$$\sum_{i=1}^n \sum_{j\in S_i} c_{ij}x_{ij}$ 

так, чтобы $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}\underset{j\in <!--\; \in \; -->S_i}{\sum <!--\; \sum \; -->}{p}_{ij}{x}_{ij}\le <!--\; \le \; -->P$$\sum_{i=1}^n \sum_{j\in S_i} p_{ij}x_{ij} \le P$  выполнялось условие на вместимость,

$\underset{j\in <!--\; \in \; -->S_i}{\sum <!--\; \sum \; -->}{x}_{ij}=1$$\sum_{j\in S_i}x_{ij}=1$  для всех $i=1,2,...,n$$i= 1,2,...,n$ 

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

Пусть у нас есть $n$$n$  предметов и $m$$m$  рюкзаков ($m\le <!--\; \le \; -->n$$m\le n$ ). У каждого предмета, как и раньше, есть вес $p_j>0$$p_j>0$  и ценность $c_j>0$$c_j>0$ $j=1,2,...,n$$j= 1,2,...,n$ , у каждого рюкзака соответственно своя вместимость $P_i$$P_{i}$  при $i=1,2,...,m$$i= 1,2,...,m$ . $x_i\in <!--\; \in \; -->0,1$$x_i \in {0,1}$ . Задача:

максимизировать $\underset{i=1}{\overset{m}{\sum <!--\; \sum \; -->}}\underset{j=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_j{x}_{ij}$$\sum _{i=1}^{m}\sum _{j=1}^{n}c_{j}x_{ij}$ 

так, чтобы $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_j{x}_{ij}\le <!--\; \le \; -->P_i$$\sum_{i=1}^n p_{j}x_{ij} \le P_i$  выполнялось условие для всех $i=1,2,...,m$$i= 1,2,...,m$ ,

$\underset{j=1}{\overset{m}{\sum <!--\; \sum \; -->}}{x}_{ij}\le <!--\; \le \; -->1$$\sum _{j=1}^{m}x_{ij}\leq 1$  для всех $i=1,2,...,n$$i= 1,2,...,n$ .

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

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

максимизировать $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{c}_i{x}_i$$\sum_{i=1}^n c_ix_i$ 

так, чтобы $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_{ij}{x}_i\le <!--\; \le \; -->P_j$$\sum_{i=1}^n p_{ij}x_i \le P_j$ , $j=1,2,...,m$$j= 1,2,...,m$ 

и $x_i\ge <!--\; \ge \; -->0$$x_i \ge 0$  для всех $i=1,2,...,n$$i= 1,2,...,n$ .

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

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

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

при условиях $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i{x}_i\le <!--\; \le \; -->P$$\sum_{i=1}^n p_ix_i \le P$ , $x\in <!--\; \in \; -->B^n$$x\in B^{n}$ , или

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

при условиях $\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{p}_i{x}_i\ge <!--\; \ge \; -->P$$\sum _{i=1}^{n}p_{i}x_{i}\geq P$ , $x\in <!--\; \in \; -->B^n$$x\in B^{n}$ .

При этом $Q$$Q$  — неотрицательно определенная матрица размера $n\times <!--\; \times \; -->n$$n\times n$ , $B^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. Алгоритм рюкзака