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

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

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

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

Многомерный рюкзак (англ. 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}$^[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. Архивная копия от 22 декабря 2012 на Wayback Machine

Ссылки[править | править код]

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