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

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

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

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

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

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

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

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

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

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

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

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

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

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

SUKP определяется Келлерером и др ^{. [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, ограниченный и неограниченный; неограниченный вариант показан ниже.

Было показано, что вариант 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, мы постараемся максимизировать количество предметов, которое не превысит вместимость рюкзака:

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

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

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

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

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

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

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

Ссылки

1. Мартелло, Сильвано и Тот, Паоло (1990). Задачи о рюкзаке: алгоритмы и компьютерные реализации. John Wiley & Sons . ISBN 978-0471924203.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Келлерер, Ганс и Пферши, Ульрих и Пизингер, Дэвид (2004). Проблемы с рюкзаком . Спрингер Верлаг . ISBN 978-3-540-40286-2.{{cite book}}: CS1 maint: multiple names: authors list (link)
3. Люкер, Г. С. (1975). Две NP-полные задачи в неотрицательном целочисленном программировании . Отчет № 178, Лаборатория компьютерных наук, Принстон.
4. Генс, Г. В.; Левнер, Э. В. (1979). «Сложность и аппроксимационные алгоритмы для комбинаторных задач: обзор». Центральный экономико-математический институт АН СССР, Москва.
5. «О существовании быстрых схем аппроксимации». Нелинейное программирование . 4 : 415–437. 1980.
6. Журнал, Майкл Дж.; Черн, Мо-Шенг (1984). «Заметка о схемах аппроксимации для многомерных задач о ранце». Математика исследования операций . 9 (2): 244–247. doi :10.1287/moor.9.2.244.
7. Коэн, Реувен; Кацир, Лиран (2008). «Обобщенная задача максимального покрытия». Information Processing Letters . 108 : 15–22. CiteSeerX 10.1.1.156.2073 . doi :10.1016/j.ipl.2008.03.017. 

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