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

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

Общим для всех видов является наличие набора из $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$ на вместимость рюкзакаШаблон:SfnШаблон:Sfn.

Ограниченный рюкзак (Шаблон: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$Шаблон:Sfn.

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

Неограниченный рюкзак (целочисленный рюкзак) (Шаблон: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$Шаблон:Sfn.

Рюкзак с мультивыбором (Шаблон: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>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}\le P_i$ выполнялось условие для всех $i=1,2,...,m$,

$\sum _{j=1}^m{x}_{ij}\le 1$ для всех $i=1,2,...,n$Шаблон:Sfn.

Многомерный рюкзак (Шаблон: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$Шаблон:Sfn.

Квадратичная задача о рюкзаке (Шаблон:Lang-en)

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

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

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

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

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

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

Литература

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

1. Шаблон:Книга

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

1. Шаблон:Книга
2. Шаблон:Книга Шаблон:Wayback

Ссылки

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