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

Задача о рюкзаке - одна из наиболее изученных проблем комбинаторной оптимизации , имеющая множество реальных приложений. По этой причине было рассмотрено множество частных случаев и обобщений. ^{[1] [2]}

Общим для всех версий является набор из n элементов, каждый из которых имеет соответствующую прибыль p _j , вес w _j . Переменная двоичного решения x _j используется для выбора элемента. Цель состоит в том, чтобы выбрать некоторые из пунктов, с максимальной общей прибылью, в то время как повиновение , что максимальный общий вес выбранных предметов не должен превышать W . Как правило, эти коэффициенты масштабируются, чтобы стать целыми числами, и почти всегда предполагается, что они положительны.${\ Displaystyle 1 \ Leq J \ Leq N}$

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

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

Прямые обобщения [ править ]

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

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

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

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

Неограниченный вариант был показан как NP-полный в 1975 году Люкером. ^[3] И ограниченный, и неограниченный варианты допускают FPTAS (по сути, такой же, как в задаче о рюкзаке 0-1).

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

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

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

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

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

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

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

Квадратичная задача о ранце :

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

Задача о ранце Союза :

SUKP определяется Kellerer et al ^[2] (на стр. 423) следующим образом:

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

Множественные ограничения [ править ]

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

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

Вариант 0-1 (для любого фиксированного ) оказался NP-полным примерно в 1980 г. и, что более важно, не имеет FPTAS, если P = NP. ^{[4] [5]}${\displaystyle m\geq 2}$

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

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

Задачи, похожие на рюкзаки [ править ]

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

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

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

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

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

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

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

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

В варианте рюкзака максимальной плотности есть начальный вес , и мы максимизируем плотность выбранных предметов, которые не нарушают ограничение вместимости: ^[7]${\displaystyle w_{0}}$

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

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

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

Последние три из них обсуждаются в справочной работе Kellerer et al., Knapsack Problems . ^[2]

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

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