Список проблем с рюкзаком

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

Общим для всех версий является набор из n элементов, каждый из которых $1\leq j\leq n$ соответствующую прибыль pj _{имеющие} и wj _вес . Двоичная переменная решения x _j используется для выбора элемента. Цель состоит в том, чтобы выбрать несколько предметов с максимальной общей прибылью, соблюдая при этом, что максимальный общий вес выбранных предметов не должен W. превышать Обычно эти коэффициенты масштабируются до целых чисел и почти всегда считаются положительными.

в Задача о рюкзаке ее самой простой форме:

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	$\forall j\in \{1,\ldots ,n\}$

Прямые обобщения

Одним из распространенных вариантов является то, что каждый элемент можно выбрать несколько раз. Задача об ограниченном рюкзаке определяет для каждого предмета j верхнюю границу u _j (которая может быть положительным целым числом или бесконечностью) количества раз, когда предмет j может быть выбран:

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$0\leq x_{j}\leq u_{j},x_{j}$ интеграл для всех j

Задача о неограниченном рюкзаке (иногда называемая задачей о целочисленном рюкзаке ) не накладывает никаких верхних границ на количество раз, когда элемент может быть выбран:

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\geq 0,x_{j}$ интеграл для всех j

показал, что неограниченный вариант является NP-полным . В 1975 году Люкер И ограниченный, и неограниченный варианты допускают FPTAS (по сути тот же, что и тот, который использовался в задаче о рюкзаке 0–1).

Если предметы разделены на k классов, обозначаемых $N_{i}$, и из каждого класса нужно взять ровно один предмет, мы получаем задачу о ранце с множественным выбором :

максимизировать $\sum _{i=1}^{k}\sum _{j\in N_{i}}p_{ij}x_{ij}$
при условии	$\sum _{i=1}^{k}\sum _{j\in N_{i}}w_{ij}x_{ij}\leq W,$
	$\sum _{j\in N_{i}}x_{ij}=1,$	для всех $1\leq i\leq k$
	$x_{ij}\in \{0,1\}$	для всех $1\leq i\leq k$ и все $j\in N_{i}$

Если для каждого предмета прибыль и вес равны, мы получаем задачу о сумме подмножества соответствующая задача решения (часто вместо этого дается ):

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}$
при условии	$\sum _{j=1}^{n}p_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$

Если у нас есть n предметов и m рюкзаков вместимостью $W_{i}$, мы получаем задачу о нескольких рюкзаках :

максимизировать $\sum _{i=1}^{m}\sum _{j=1}^{n}p_{j}x_{ij}$
при условии	$\sum _{j=1}^{n}w_{j}x_{ij}\leq W_{i},$	для всех $1\leq i\leq m$
	$\sum _{i=1}^{m}x_{ij}\leq 1,$	для всех $1\leq j\leq n$
	$x_{ij}\in \{0,1\}$	для всех $1\leq j\leq n$ и все $1\leq i\leq m$

В качестве частного случая задачи о множественных рюкзаках, когда прибыль равна весу и все контейнеры имеют одинаковую вместимость, мы можем столкнуться с проблемой суммы множественных подмножеств .

Задача о квадратичном рюкзаке :

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}+\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}p_{ij}x_{i}x_{j}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\}$	для всех $1\leq j\leq n$

Задача о рюкзаке Set-Union :

SUKP определен Келлерером и др. (на странице 423) следующим образом:

Учитывая набор $n$ предметы $N=\{1,\ldots ,n\}$ и набор $m$ так называемые элементы $P=\{1,\ldots ,m\}$, каждый предмет $j$ соответствует подмножеству $P_{j}$ набора элементов $P$. Предметы $j$ иметь неотрицательную прибыль $p_{j}$, $j=1,\ldots ,n$, и элементы $i$ иметь неотрицательный вес $w_{i}$, $i=1,\ldots ,m$. Общий вес набора предметов определяется суммарным весом элементов объединения соответствующих наборов элементов. Цель состоит в том, чтобы найти подмножество предметов, общий вес которых не превышает вместимости рюкзака, и максимальную прибыль.

Множественные ограничения

Если существует более одного ограничения (например, ограничение по объему и ограничение по весу, где объем и вес каждого предмета не связаны между собой), мы получаем задачу о рюкзаке с множественными ограничениями , задачу о многомерном рюкзаке или m - мерную задачу. проблема с рюкзаком . (Обратите внимание, что здесь «размер» не относится к форме каких-либо предметов.) Он имеет варианты 0–1, ограниченный и неограниченный; неограниченный показан ниже.

максимизировать $\sum _{j=1}^{n}p_{j}x_{j}$
при условии	$\sum _{j=1}^{n}w_{ij}x_{j}\leq W_{i},$	для всех $1\leq i\leq m$
	$x_{j}\geq 0$, $x_{j}$ целое число	для всех $1\leq j\leq n$

Вариант 0-1 (для любого фиксированного $m\geq 2$) было показано, что он NP-полный примерно в 1980 году и более строго, не имеет FPTAS, если только P = NP.

Ограниченный и неограниченный варианты (при любом фиксированном $m\geq 2$) также обладают такой же твердостью.

Для любого фиксированного $m\geq 2$, эти задачи допускают алгоритм псевдополиномиального времени (аналогичный алгоритму для базового рюкзака) и PTAS .

Проблемы с рюкзаком

Если все прибыли равны 1, мы постараемся максимизировать количество предметов, не превышающее вместимость рюкзака:

максимизировать $\sum _{j=1}^{n}x_{j}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Если у нас есть несколько контейнеров (одного размера) и мы хотим упаковать все n предметов в как можно меньшее количество контейнеров, мы получаем проблему упаковки корзин , которая моделируется с помощью индикаторных переменных. $y_{i}=1\Leftrightarrow$ контейнер i используется:

минимизировать $\sum _{i=1}^{n}y_{i}$
при условии	$\sum _{j=1}^{n}w_{j}x_{ij}\leq Wy_{i},$	$\forall i\in \{1,\ldots ,n\}$
	$\sum _{i=1}^{n}x_{ij}=1$	$\forall j\in \{1,\ldots ,n\}$
	$y_{i}\in \{0,1\}$	$\forall i\in \{1,\ldots ,n\}$
	$x_{ij}\in \{0,1\}$	$\forall i\in \{1,\ldots ,n\}\wedge \forall j\in \{1,\ldots ,n\}$

Задача о сокращении запасов идентична задаче об упаковке корзин , но поскольку в практических примерах обычно используется гораздо меньше типов товаров, часто используется другая формулировка. Предмет j необходим B _j раз, каждый «шаблон» предметов, помещающихся в один рюкзак, имеет переменную x _i (имеется m шаблонов), а шаблон i использует предмет j b _ij раз:

минимизировать $\sum _{i=1}^{m}x_{i}$
при условии	$\sum _{i=1}^{m}b_{ij}x_{i}\geq B_{j},$	для всех $1\leq j\leq n$
	$x_{i}\in \{0,1,\ldots ,n\}$	для всех $1\leq i\leq m$

Если к задаче о рюкзаке с множественным выбором мы добавим ограничение, согласно которому каждое подмножество имеет размер n , и удалим ограничение на общий вес, мы получим задачу назначения , которая также является проблемой поиска максимального двустороннего паросочетания :

максимизировать $\sum _{i=1}^{k}\sum _{j=1}^{n}p_{ij}x_{ij}$
при условии	$\sum _{i=1}^{n}x_{ij}=1,$	для всех $1\leq j\leq n$
	$\sum _{j=1}^{n}x_{ij}=1,$	для всех $1\leq i\leq n$
	$x_{ij}\in \{0,1\}$	для всех $1\leq i\leq k$ и все $j\in N_{i}$

В варианте ранца максимальной плотности присутствует начальный вес. $w_{0}$, и мы максимизируем плотность выбранных элементов, которые не нарушают ограничение мощности:

максимизировать ${\frac {\sum _{j=1}^{n}x_{j}p_{j}}{w_{0}+\sum _{j=1}^{n}x_{j}w_{j}}}$
при условии	$\sum _{j=1}^{n}w_{j}x_{j}\leq W,$
	$x_{j}\in \{0,1\},$	$\forall j\in \{1,\ldots ,n\}$

Хотя они менее распространены, чем описанные выше, существуют и другие проблемы, похожие на рюкзак, в том числе:

• Задача о вложенном рюкзаке
• Проблема сворачивающегося рюкзака
• Нелинейная задача о рюкзаке
• Обратно-параметрическая задача о рюкзаке

Последние три из них обсуждаются в справочной работе Келлерера и др «Задачи о рюкзаке» . .

Ссылки

• «Алгоритмы решения задач о рюкзаке» , Д. Пизингер. доктор философии диссертация, DIKU, Копенгагенский университет, Отчет 95/1 (1995).