WikiSort.ru - Не сортированное

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

Общим для всех видов является наличие набора из ${\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}$ на вместимость рюкзака^[1][2].

Ограниченный рюкзак (англ. 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}$ ^[3].

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

Неограниченный рюкзак (целочисленный рюкзак) (англ. 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}$ ^[4].

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

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

Многомерный рюкзак (англ. Multy-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}$ ^[4].

Квадратичная задача о рюкзаке (англ. 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}}$ задаёт ограничения на количество предметов^[6].

Примечания

Литература

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

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

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

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

Ссылки

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