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

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

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

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

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

при наличии ограничения ${\displaystyle \sum _{i=1}^{n}p_{i}x_{i}\leq P}$ на вместимость рюкзака .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

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

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

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

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

Ссылки