Задача о рюкзаке - Knapsack problem

Пример одномерной (ограниченной) задачи о рюкзаке: какие коробки следует выбрать, чтобы максимизировать количество денег, сохраняя при этом общий вес не более 15 кг? А проблема с множественными ограничениями мог учитывать как вес, так и объем ящиков.
(Решение: если доступно любое количество каждого поля, то три желтых поля и три серых поля; если доступны только показанные поля, то все, кроме зеленого поля.)

В проблема с рюкзаком проблема в комбинаторная оптимизация: Учитывая набор элементов, каждый из которых имеет вес и значение, определите количество каждого элемента, который нужно включить в коллекцию, чтобы общий вес был меньше или равнялся заданному пределу, а общее значение было как можно большим. Он получил свое название от проблемы, с которой сталкивается кто-то, кто ограничен фиксированным размером рюкзак и должен наполнить его самыми ценными предметами. Проблема часто возникает в распределение ресурсов где лица, принимающие решения, должны выбирать из набора неделимых проектов или задач с фиксированным бюджетом или временными ограничениями соответственно.

Проблема рюкзака изучается более века, ранние работы относятся к 1897 году.^[1] Название «задача о рюкзаке» восходит к ранним работам математика. Тобиас Данциг (1884–1956),^[2] и относится к банальной проблеме упаковки наиболее ценных или полезных вещей без перегрузки багажа.

Приложения

Исследование репозитория алгоритмов Университета Стони Брук в 1999 г. показало, что из 75 алгоритмических задач задача о рюкзаке была 19-й по популярности и третьей по популярности после суффиксные деревья и проблема с упаковкой бункера.^[3]

Проблемы с рюкзаком возникают в реальных процессах принятия решений в самых разных областях, таких как поиск наименее расточительного способа резки сырья,^[4] выбор инвестиции и портфели,^[5] подбор активов для секьюритизация, обеспеченная активами,^[6] и генерация ключей для Меркл – Хеллман^[7] и другие ранцевых криптосистем.

Одним из первых применений алгоритмов ранца было построение и оценка тестов, в которых испытуемые имели возможность выбирать, на какие вопросы им отвечать. Для небольших примеров предоставить испытуемым такой выбор - довольно простой процесс. Например, если экзамен содержит 12 вопросов, каждый из которых оценивается в 10 баллов, тестируемому нужно ответить только на 10 вопросов, чтобы получить максимально возможную оценку в 100 баллов. Однако в тестах с неоднородным распределением баллов сделать выбор труднее. Фейерман и Вайс предложили систему, в которой студентам дают разнородный тест, в котором можно набрать 125 возможных баллов. Учащимся предлагается ответить на все вопросы в меру своих возможностей. Из возможных подмножеств задач, общая сумма баллов которых составляет в сумме 100, алгоритм ранца определит, какое подмножество дает каждому ученику максимально возможную оценку.^[8]

Определение

Чаще всего решается проблема 0-1 задача о ранце, что ограничивает количество ${displaystyle x_ {i}}$ копий каждого вида элемента до нуля или одного. Учитывая набор ${displaystyle n}$ элементы пронумерованы от 1 до ${displaystyle n}$ , каждый с весом ${displaystyle w_ {i}}$ и ценность ${displaystyle v_ {i}}$ , наряду с максимальной грузоподъемностью ${displaystyle W}$ ,

максимизировать

{displaystyle sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

при условии

{displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}

и

{displaystyle x_ {i} в {0,1}}

.

Здесь ${displaystyle x_ {i}}$ представляет количество экземпляров элемента ${displaystyle i}$ включить в рюкзак. Неформально проблема состоит в том, чтобы максимизировать сумму значений предметов в рюкзаке, чтобы сумма весов была меньше или равнялась вместимости рюкзака.

В ограниченная задача о рюкзаке (БКП) снимает ограничение на наличие только одного элемента каждого элемента, но ограничивает количество ${displaystyle x_ {i}}$ копий каждого вида элементов до максимального неотрицательного целого числа ${displaystyle c}$ :

максимизировать

{displaystyle sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

при условии

{displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}

и

{displaystyle x_ {i} in {0,1,2, dots, c}.}

В неограниченная задача о рюкзаке (УКП) не устанавливает верхней границы количества копий каждого вида элементов и может быть сформулирован, как указано выше, за исключением того, что единственное ограничение на ${displaystyle x_ {i}}$ в том, что это неотрицательное целое число.

максимизировать

{displaystyle sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

при условии

{displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i} leq W}

и

{displaystyle x_ {i} geq 0, x_ {i} в mathbb {Z}.}

Один из примеров задачи о неограниченном рюкзаке дается с использованием рисунка, показанного в начале этой статьи, и текста «если доступно любое количество каждого ящика» в заголовке этого рисунка.

Вычислительная сложность

Задача о рюкзаке интересна с точки зрения информатики по многим причинам:

В проблема решения форма задачи о ранце (Может ли значение не менее V достигать без превышения веса W?) является НП-полный, таким образом, не существует известного алгоритма одновременно правильного и быстрого (полиномиального времени) во всех случаях.
В то время как проблема решения является NP-полной, проблема оптимизации - нет, ее решение по крайней мере так же сложно, как и проблема решения, и не существует известного полиномиального алгоритма, который мог бы сказать, учитывая решение, является ли оно оптимальным (что означало бы что нет решения с большим V, решая таким образом NP-полную задачу решения).
Существует псевдополиномиальное время алгоритм с использованием динамическое программирование.
Существует полностью полиномиальная схема аппроксимации, который использует алгоритм псевдополиномиального времени в качестве подпрограммы, описанной ниже.
Тем не менее, многие случаи, возникающие на практике, и «случайные экземпляры» из некоторых распределений могут быть решены точно.

Существует связь между проблемами «решения» и «оптимизации» в том смысле, что если существует полиномиальный алгоритм, который решает проблему «решения», то можно найти максимальное значение для задачи оптимизации за полиномиальное время, применяя этот алгоритм итеративно, пока увеличивая значение k. С другой стороны, если алгоритм находит оптимальное значение задачи оптимизации за полиномиальное время, то проблема решения может быть решена за полиномиальное время путем сравнения значения решения, полученного этим алгоритмом, со значением k. Таким образом, обе версии проблемы имеют одинаковую сложность.

Одна из тем в исследовательской литературе - определить, как выглядят «сложные» примеры задачи о рюкзаке.^[9]^[10] или взглянуть с другой стороны, чтобы определить, какие свойства экземпляров на практике могут сделать их более податливыми, чем предполагает их NP-полное поведение наихудшего случая.^[11] Целью поиска этих "сложных" экземпляров является их использование в криптография с открытым ключом системы, такие как Ранцевая криптосистема Меркла-Хеллмана.

Кроме того, примечателен тот факт, что сложность задачи о рюкзаке зависит от формы ввода. Если веса и прибыль даны как целые числа, это слабо NP-полный, пока это сильно NP-полный если веса и прибыль даны в виде рациональных чисел.^[12] Однако в случае рациональных весов и прибылей он все же допускает полностью полиномиальная схема аппроксимации.

Решение

Для решения задач о рюкзаке доступно несколько алгоритмов, основанных на подходе динамического программирования.^[13] то ветвь и переплет подход^[14] или же гибридизации обоих подходов.^[11]^[15]^[16]^[17]

Алгоритм предварительного динамического программирования

В неограниченная задача о рюкзаке (УКП) не накладывает ограничений на количество копий каждого вида товаров. Кроме того, здесь мы предполагаем, что ${displaystyle x_ {i}> 0}$

{displaystyle m [w '] = max left (сумма _ {i = 1} ^ {n} v_ {i} x_ {i} ight)}

при условии

{displaystyle sum _ {i = 1} ^ {n} w_ {i} x_ {i} leq w '}

и

{displaystyle x_ {i}> 0}

Заметьте, что ${displaystyle m [w]}$ обладает следующими свойствами:

1. ${displaystyle m [0] = 0 ,!}$ (сумма нулевых элементов, т.е. сумма пустого множества).

2. ${displaystyle m [w] = max (v_ {1} + m [w-w_ {1}], v_ {2}] + m [w-w_ {2}], ..., v_ {i} + m [ w-w_ {i}])}$ , ${displaystyle w_ {i} leq w}$ , куда ${displaystyle v_ {i}}$ стоимость ${displaystyle i}$ -й вид предметов.

Второе свойство требует подробного объяснения. В процессе выполнения этого метода, как мы получаем вес ${displaystyle w}$ ? Есть только ${displaystyle i}$ пути и предыдущие веса ${displaystyle w-w_ {1}, w-w_ {2}, ..., w-w_ {i}}$ где есть всего ${displaystyle i}$ виды разных предметов (говоря разные, мы имеем в виду, что вес и стоимость не совсем одинаковы). Если мы знаем каждое значение этих ${displaystyle i}$ элементы и соответствующее максимальное значение ранее, мы просто сравниваем их друг с другом и в конечном итоге получаем максимальное значение, и все готово.

Здесь максимум пустого множества принимается равным нулю. Табулирование результатов ${displaystyle m [0]}$ вверх через ${displaystyle m [W]}$ дает решение. Поскольку расчет каждого ${displaystyle m [w]}$ включает изучение не более ${displaystyle n}$ предметов, и их не более ${displaystyle W}$ ценности ${displaystyle m [w]}$ для расчета время работы решения динамического программирования составляет ${displaystyle O (nW)}$ . Разделение ${displaystyle w_ {1} ,, w_ {2} ,, ldots ,, w_ {n} ,, W}$ по их наибольший общий делитель это способ улучшить время работы.

Даже если P ≠ NP, то ${displaystyle O (nW)}$ сложность не противоречит тому, что задача о рюкзаке НП-полный, поскольку ${displaystyle W}$ , В отличие от ${displaystyle n}$ , не является полиномиальным по длине входа в задачу. Длина ${displaystyle W}$ вход в задачу пропорционален количеству бит в ${displaystyle W}$ , ${displaystyle log W}$ , а не ${displaystyle W}$ сам. Однако, поскольку эта среда выполнения псевдополином, это делает (вариант решения) задачу о ранце слабо NP-полная задача.

0-1 задача о ранце

Аналогичное решение динамического программирования для задачи о ранце 0-1 также выполняется за псевдополиномиальное время. Предполагать ${displaystyle w_ {1} ,, w_ {2} ,, ldots ,, w_ {n} ,, W}$ - строго положительные целые числа. Определять ${displaystyle m [i, w]}$ быть максимальным значением, которое может быть достигнуто при весе меньше или равном ${displaystyle w}$ с использованием предметов до ${displaystyle i}$ (первый ${displaystyle i}$ Предметы).

Мы можем определить ${displaystyle m [i, w]}$ рекурсивно следующим образом: (Определение А)

${displaystyle m [0,, w] = 0}$
${displaystyle m [i ,, w] = m [i-1,, w]}$ если ${displaystyle w_ {i}> w ,!}$ (вес нового товара превышает текущий лимит)
${displaystyle m [i ,, w] = max (m [i-1,, w] ,, m [i-1, w-w_ {i}] + v_ {i})}$ если ${displaystyle w_ {i} leqslant w}$ .

Затем решение можно найти, вычислив ${displaystyle m [n, W]}$ . Чтобы сделать это эффективно, мы можем использовать таблицу для хранения предыдущих вычислений.

Ниже приводится псевдокод динамической программы:

 1 // Вход: 2 // Значения (хранятся в массиве v) 3 // Вес (хранится в массиве w) 4 // Количество отдельных элементов (n) 5 // Вместимость ранца (Вт) 6 // ПРИМЕЧАНИЕ. Предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1. 7  8 за j из 0 к W делать: 9     м[0, j] := 010 11 за я из 1 к п делать:12     за j из 0 к W делать:13         если ш[я] > j тогда:14             м[я, j] := м[я-1, j]15         еще:16             м[я, j] := Максимум(м[я-1, j], м[я-1, j-ш[я]] + v[я])

Поэтому это решение будет работать в ${displaystyle O (nW)}$ время и ${displaystyle O (nW)}$ Космос.

Однако, если мы сделаем еще один или два шага дальше, мы должны знать, что метод будет работать в промежутке времени между ${displaystyle O (nW)}$ и ${displaystyle O (2 ^ {n})}$ . Из Определение А, мы можем знать, что нет необходимости вычислять все веса, когда количество элементов и сами элементы, которые мы выбрали, фиксированы. Другими словами, приведенная выше программа вычисляет больше, чем ожидалось, потому что вес все время меняется с 0 на W. Все, что нам нужно сделать, это сравнить m [i-1, j] и m [i-1, jw [i]] + v [i] для m [i, j], и когда m [i-1, jw [i]] вне допустимого диапазона, мы просто передаем значение m [i-1, j] в m [i, j]. С этой точки зрения мы можем запрограммировать этот метод так, чтобы он выполнялся рекурсивно.

 1 // Вход: 2 // Значения (хранятся в массиве v) 3 // Вес (хранится в массиве w) 4 // Количество отдельных элементов (n) 5 // Вместимость ранца (Вт) 6 // ПРИМЕЧАНИЕ. Предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1. 7  8 Определять ценить[п, W] 9 10 Инициализировать Все ценить[я, j] = -111 12 Определять м:=(я,j)         // Определим функцию m так, чтобы она представляла максимальное значение, которое мы можем получить при условии: использовать первые i элементов, общий предел веса равен j13 {14     если я == 0 или же j <= 0 тогда:15         ценить[я, j] = 016         возвращаться17 18     если (ценить[я-1, j] == -1) тогда:     // m [i-1, j] не вычислено, необходимо вызвать функцию m19         ценить[я-1, j] = м(я-1, j)20 21     если ш[я] > j тогда:                      // товар не помещается в сумку (ЭТО НЕ УДАЛОСЬ В ПРЕДЫДУЩЕМ АЛГОРИТМЕ)22         ценить[я, j] = ценить[я-1, j]23     еще: 24         если (ценить[я-1, j-ш[я]] == -1) тогда:     // m [i-1, j-w [i]] не вычислено, мы должны вызвать функцию m25             ценить[я-1, j-ш[я]] = м(я-1, j-ш[я])26         ценить[я, j] = Максимум(ценить[я-1,j], ценить[я-1, j-ш[я]] + v[я])27 }28 29 Пробег м(п, W)

Например, есть 10 различных предметов, а ограничение по весу - 67. Итак,

{displaystyle {egin {выровнено} & w [1] = 23, w [2] = 26, w [3] = 20, w [4] = 18, w [5] = 32, w [6] = 27, w [7] = 29, w [8] = 26, w [9] = 30, w [10] = 27 & v [1] = 505, v [2] = 352, v [3] = 458, v [ 4] = 220, v [5] = 354, v [6] = 414, v [7] = 498, v [8] = 545, v [9] = 473, v [10] = 543 end {выровнено }}}

Если вы используете вышеуказанный метод для вычисления ${displaystyle m (10,67)}$ , ты получишь (за исключением вызовов, которые производят m (i, j) = 0):

{displaystyle {egin {выровнено} & m (10,67) = 1270 & m (9,67) = 1270, m (9,40) = 678 & m (8,67) = 1270, m (8,40) = 678, m (8,37) = 545 & m (7,67) = 1183, m (7,41) = 725, m (7,40) = 678, m (7,37) = 505 & m (6 , 67) = 1183, m (6,41) = 725, m (6,40) = 678, m (6,38) = 678, m (6,37) = 505 & m (5,67) = 1183 , m (5,41) = 725, m (5,40) = 678, m (5,38) = 678, m (5,37) = 505 & m (4,67) = 1183, m (4, 41) = 725, m (4,40) = 678, m (4,38) = 678, m (4,37) = 505, m (4,35) = 505 & m (3,67) = 963, m (3,49) = 963, m (3,41) = 505, m (3,40) = 505, m (3,38) = 505, m (3,37) = 505, m (3,35) ) = 505, m (3,23) = 505, m (3,22) = 458, m (3,20) = 458 & m (2,67) = 857, m (2,49) = 857, м (2,47) = 505, m (2,41) = 505, m (2,40) = 505, m (2,38) = 505, m (2,37) = 505, m (2,35) = 505, m (2,29) = 505, m (2,23) = 505 & m (1,67) = 505, m (1,49) = 505, m (1,47) = 505, m ( 1,41) = 505, m (1,40) = 505, m (1,38) = 505, m (1,37) = 505, m (1,35) = 505, m (1,29) = 505, м (1,23) = 505 end {align}}}

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

Встреча посередине

Другой алгоритм для ранца 0-1, открытый в 1974 году.^[18] и иногда называется "встречей посередине" из-за параллелей с аналогично названный алгоритм в криптографии, является экспоненциальной по количеству различных элементов, но может быть предпочтительнее алгоритма DP, когда ${displaystyle W}$ большой по сравнению с п. В частности, если ${displaystyle w_ {i}}$ неотрицательные, но не целые числа, мы все равно могли бы использовать алгоритм динамического программирования, масштабируя и округляя (т.е. используя арифметика с фиксированной точкой ), но если проблема требует ${displaystyle d}$ дробные цифры точности для получения правильного ответа, ${displaystyle W}$ нужно будет масштабировать на ${displaystyle 10 ^ {d}}$ , а алгоритм DP потребует ${displaystyle O (W10 ^ {d})}$ пространство и ${displaystyle O (nW10 ^ {d})}$ время.

алгоритм Встреча посередине является    Вход: Набор предметов с весами и значениями. выход: Наибольшее комбинированное значение подмножества. разбить множество {1 ...п} на два набора А и B приблизительно равного размера вычислить веса и значения всех подмножеств каждого набора для каждого подмножество из А делать        найти подмножество B наибольшего значения, при котором общий вес меньше W    отслеживать наибольшую совокупную ценность, замеченную до сих пор

Алгоритм принимает ${displaystyle O (2 ^ {n / 2})}$ пространства, и эффективные реализации шага 3 (например, сортировка подмножеств B по весу, отбрасывание подмножеств B, которые весят больше, чем другие подмножества B большего или равного значения, и использование двоичного поиска для поиска наилучшего соответствия) приводят к время выполнения ${displaystyle O (n2 ^ {n / 2})}$ . Как и в случае с встретиться в середине атаки в криптографии это улучшает ${displaystyle O (n2 ^ {n})}$ время выполнения наивного подхода грубой силы (изучение всех подмножеств ${displaystyle {1 ... n}}$ ) за счет использования экспоненциального, а не постоянного пространства (см. также бэби-шаг гигантский шаг ).

Алгоритмы аппроксимации

Что касается большинства NP-полных проблем, этого может быть достаточно, чтобы найти работоспособные решения, даже если они не оптимальны. Однако предпочтительно приближение дает гарантию разницы между значением найденного решения и значением оптимального решения.

Как и в случае со многими полезными, но сложными в вычислительном отношении алгоритмами, были проведены существенные исследования по созданию и анализу алгоритмов, приближающих решение. Задача о ранце, хотя и NP-Hard, является одним из набора алгоритмов, которые все еще могут быть аппроксимированы до любой указанной степени. Это означает, что задача имеет схему аппроксимации полиномиальным временем. Точнее говоря, задача о рюкзаке имеет полностью полиномиальную схему аппроксимации по времени (FPTAS).^[19]

Алгоритм жадного приближения

Джордж Данциг предложил жадный алгоритм аппроксимации решить неограниченную задачу о ранце.^[20] Его версия сортирует предметы в порядке убывания стоимости на единицу веса, ${displaystyle v_ {1} / w_ {1} geq cdots geq v_ {n} / w_ {n}}$ . Затем он вставляет их в мешок, начиная с максимально возможного количества копий предметов первого типа, пока в мешке не останется места для новых. При условии, что есть неограниченный запас каждого вида предметов, если ${displaystyle m}$ - максимальное количество предметов, которые помещаются в мешок, тогда жадный алгоритм гарантированно достигнет хотя бы значения ${displaystyle m / 2}$ .

Для ограниченной задачи, когда предложение каждого вида предметов ограничено, приведенный выше алгоритм может быть далек от оптимального. Тем не менее, простая модификация позволяет решить этот случай: Построить решение ${displaystyle S_ {1}}$ упаковывая предметы как можно дольше с жадностью, т.е. ${displaystyle S_ {1} = left {1, ldots, kight}}$ куда ${displaystyle k = extstyle max _ {1leq k'leq n} extstyle sum _ {i = 1} ^ {k} w_ {i} leq W}$ . Кроме того, построим второе решение ${displaystyle S_ {2} = left {k + 1ight}}$ содержащий первый элемент, который не подошел. С ${displaystyle S_ {1} чашка S_ {2}}$ дает верхнюю границу для LP релаксация задачи, один из наборов должен иметь значение не менее ${displaystyle m / 2}$ ; таким образом мы возвращаем то, что из ${displaystyle S_ {1}}$ и ${displaystyle S_ {2}}$ имеет лучшее значение для получения ${displaystyle 1/2}$ -приближение.

Схема аппроксимации полностью полиномиальным временем

В полностью полиномиальная схема аппроксимации по времени (FPTAS) для задачи о рюкзаке использует тот факт, что причина, по которой проблема не имеет известных решений за полиномиальное время, состоит в том, что прибыль, связанная с предметами, не ограничена. Если округлить некоторые из наименее значащих цифр значений прибыли, то они будут ограничены полиномом и 1 / ε, где ε - оценка правильности решения. Это ограничение означает, что алгоритм может найти решение за полиномиальное время, которое является правильным в пределах коэффициента (1-ε) от оптимального решения.^[19]

алгоритм FPTAS является     Вход: ε ∈ (0,1] список A из n элементов, заданных их значениями,  ${displaystyle v_ {i}}$ , и веса выход: S 'решение FPTAS P: = max  ${displaystyle {v_ {i} mid 1leq ileq n}}$   // максимальное значение элемента K: = ε  ${displaystyle {frac {P} {n}}}$     за я из 1 к п делать         ${displaystyle v '_ {i}}$  :=  ${displaystyle leftlfloor {frac {v_ {i}} {K}} ightfloor}$     конец для    возвращаться решение S ', используя  ${displaystyle v '_ {i}}$  значения в динамической программе, описанной выше

Теорема: Набор ${displaystyle S '}$ вычисленный по приведенному выше алгоритму удовлетворяет ${displaystyle mathrm {profit} (S ') geq (1-varepsilon) cdot mathrm {profit} (S ^ {*})}$ , куда ${displaystyle S ^ {*}}$ оптимальное решение.

Отношения доминирования

Решить проблему неограниченного рюкзака можно легче, выбрасывая предметы, которые никогда не понадобятся. Для данного товара ${displaystyle i}$ , предположим, мы смогли найти набор предметов ${displaystyle J}$ такой, что их общий вес меньше веса ${displaystyle i}$ , а их суммарное значение больше, чем значение ${displaystyle i}$ . потом ${displaystyle i}$ не может появиться в оптимальном решении, потому что мы всегда можем улучшить любое потенциальное решение, содержащее ${displaystyle i}$ заменив ${displaystyle i}$ с набором ${displaystyle J}$ . Поэтому мы можем не учитывать ${displaystyle i}$ -й элемент целиком. В таких случаях, ${displaystyle J}$ говорят доминировать ${displaystyle i}$ . (Обратите внимание, что это не относится к задачам с ограниченным рюкзаком, так как мы, возможно, уже израсходовали предметы в ${displaystyle J}$ .)

Обнаружение отношений доминирования позволяет нам значительно уменьшить размер области поиска. Есть несколько разных типов отношения доминирования,^[11] которые все удовлетворяют неравенству вида:

${displaystyle qquad sum _ {jin J} w_ {j}, x_ {j} leq alpha, w_ {i}}$ , и ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq alpha, v_ {i},}$ для некоторых ${displaystyle xin Z _ {+} ^ {n}}$

куда ${displaystyle alpha in Z _ {+} ,, Jsubsetneq N}$ и ${displaystyle iot in J}$ . Вектор ${displaystyle x}$ обозначает количество копий каждого члена ${displaystyle J}$ .

Коллективное господство: В ${displaystyle i}$ -й элемент коллективно доминируют к ${displaystyle J}$ , записанный как ${displaystyle ill J}$ , если общий вес некоторой комбинации предметов в ${displaystyle J}$ меньше чем ш_я и их общая стоимость больше, чем v_я. Формально, ${displaystyle sum _ {jin J} w_ {j}, x_ {j} leq w_ {i}}$ и ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq v_ {i}}$ для некоторых ${displaystyle xin Z _ {+} ^ {n}}$ , т.е. ${displaystyle alpha = 1}$ . Проверить это доминирование сложно с вычислительной точки зрения, поэтому его можно использовать только с подходом динамического программирования. Фактически, это эквивалентно решению меньшей задачи о рюкзаке, где ${displaystyle V = v_ {i}}$ , ${displaystyle W = w_ {i}}$ , а элементы ограничены ${displaystyle J}$ .
Пороговое доминирование: В ${displaystyle i}$ -й элемент порог преобладает к ${displaystyle J}$ , записанный как ${displaystyle iprec Prec J}$ , если некоторое количество копий ${displaystyle i}$ преобладают ${displaystyle J}$ . Формально, ${displaystyle sum _ {jin J} w_ {j}, x_ {j} leq alpha, w_ {i}}$ , и ${displaystyle sum _ {jin J} v_ {j}, x_ {j} geq alpha, v_ {i},}$ для некоторых ${displaystyle xin Z _ {+} ^ {n}}$ и ${displaystyle alpha geq 1}$ . Это обобщение коллективного доминирования, впервые введенное в^[13] и используется в алгоритме EDUK. Самый маленький такой ${displaystyle alpha}$ определяет порог пункта ${displaystyle i}$ , написано ${displaystyle t_ {i} = (альфа -1) w_ {i}}$ . В этом случае оптимальное решение может содержать не более ${displaystyle alpha -1}$ копии ${displaystyle i}$ .
Множественное доминирование: В ${displaystyle i}$ -й элемент многократно преобладают по одной позиции ${displaystyle j}$ , записанный как ${displaystyle ill _ {m} j}$ , если ${displaystyle i}$ преобладает некоторое количество копий ${displaystyle j}$ . Формально, ${displaystyle w_ {j}, x_ {j} leq w_ {i}}$ , и ${displaystyle v_ {j}, x_ {j} geq v_ {i}}$ для некоторых ${displaystyle x_ {j} in Z _ {+}}$ т.е. ${displaystyle J = {j}, alpha = 1, x_ {j} = lfloor {frac {w_ {i}} {w_ {j}}} floor}$ . Это преобладание можно эффективно использовать во время предварительной обработки, поскольку его относительно легко обнаружить.
Модульное доминирование: Позволять ${displaystyle b}$ быть лучший предмет, т.е. ${displaystyle {frac {v_ {b}} {w_ {b}}} geq {frac {v_ {i}} {w_ {i}}},}$ для всех ${displaystyle i}$ . Это предмет с наибольшей плотностью стоимости. В ${displaystyle i}$ -й элемент модульное доминирование по одной позиции ${displaystyle j}$ , записанный как ${displaystyle ill _ {Equiv} j}$ , если ${displaystyle i}$ преобладают ${displaystyle j}$ плюс несколько копий ${displaystyle b}$ . Формально, ${displaystyle w_ {j} + tw_ {b} leq w_ {i}}$ , и ${displaystyle v_ {j} + tv_ {b} geq v_ {i}}$ т.е. ${displaystyle J = {b, j}, alpha = 1, x_ {b} = t, x_ {j} = 1}$ .

Вариации

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

Задача о многоцелевом рюкзаке

Этот вариант меняет цель индивидуального наполнения рюкзака. Вместо одной цели, такой как максимизация денежной прибыли, цель может иметь несколько измерений. Например, могут быть экологические или социальные проблемы, а также экономические цели. Часто решаемые проблемы включают оптимизацию портфеля и транспортной логистики.^[21]^[22]

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

Многомерная задача о рюкзаке

В этом варианте вес рюкзака ${displaystyle i}$ задается D-мерным вектором ${displaystyle {overline {w_ {i}}} = (w_ {i1}, ldots, w_ {iD})}$ а рюкзак имеет D-мерный вектор вместимости ${displaystyle (W_ {1}, ldots, W_ {D})}$ . Цель состоит в том, чтобы максимизировать сумму значений предметов в рюкзаке так, чтобы сумма весов в каждом измерении ${displaystyle d}$ не превышает ${displaystyle W_ {d}}$ .

Многомерный рюкзак в вычислительном отношении сложнее, чем рюкзак; даже для ${displaystyle D = 2}$ , проблема не имеет EPTAS если P ${displaystyle =}$ Н.П.^[23] Однако алгоритм в^[24] показано, как эффективно решать разреженные экземпляры. Экземпляр многомерного рюкзака является разреженным, если есть набор ${displaystyle J = {1,2, ldots, m}}$ за ${displaystyle m$ так что для каждого предмета рюкзака ${displaystyle i}$ , ${displaystyle существует z> m}$ такой, что ${displaystyle forall jin Jcup {z}, w_ {ij} geq 0}$ и ${displaystyle forall yotin Jcup {z}, w_ {iy} = 0}$ . Такие случаи возникают, например, при планировании пакетов в беспроводной сети с узлами ретрансляции.^[24] Алгоритм от^[24] также решает редкие примеры варианта с множественным выбором, многомерного рюкзака с множественным выбором.

Алгоритм IHS (полка увеличения высоты) оптимален для 2D-рюкзака (упаковка квадратов в двумерный квадрат единичного размера): когда в оптимальной упаковке находится не более пяти квадратов.^[25]

Задача с несколькими рюкзаками

Этот вариант похож на Проблема с упаковкой бункера. Он отличается от Задачи упаковки ящиков тем, что можно выбрать подмножество элементов, тогда как в Задаче упаковки ящиков все предметы должны быть упакованы в определенные ящики. Идея состоит в том, что есть несколько ранцев. Это может показаться тривиальным изменением, но оно не эквивалентно увеличению вместимости исходного ранца. Этот вариант используется во многих задачах загрузки и планирования в исследовании операций и имеет Схема полиномиальной аппроксимации.^[26]

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

Квадратичная задача о рюкзаке максимизирует квадратичную целевую функцию с учетом двоичных и линейных ограничений емкости.^[27] Проблема была предложена Галло, Хаммером и Симеоне в 1980 г.^[28] однако первое рассмотрение проблемы относится к Витцгаллу в 1975 году.^[29]

Проблема подмножества суммы

В проблема суммы подмножества является частным случаем решения и задач 0-1, где вес каждого вида элемента равен значению: ${displaystyle w_ {i} = v_ {i}}$ . В области криптография, период, термин проблема с рюкзаком часто используется для обозначения проблемы суммы подмножества и широко известен как один из 21 NP-полная задача Карпа.^[30]

Обобщение проблемы суммы подмножества называется проблемой суммы нескольких подмножеств, в которой существует несколько бункеров с одинаковой емкостью. Было показано, что обобщение не имеет FPTAS.^[31]

Смотрите также

Примечания

^ Мэтьюз, Г. Б. (25 июня 1897 г.). «О разделении чисел» (PDF). Труды Лондонского математического общества. 28: 486–490. Дои:10.1112 / плмс / с1-28.1.486.
^ Данциг, Тобиас. Числа: язык науки, 1930.
^ Скиена, С. С. (сентябрь 1999 г.). «Кто интересуется алгоритмами и почему? Уроки из репозитория алгоритмов Стоуни-Брук». Новости ACM SIGACT. 30 (3): 65–74. CiteSeerX 10.1.1.41.8357. Дои:10.1145/333623.333627. ISSN 0163-5700. S2CID 15619060.
^ Келлерер, Пферши и Писингер 2004, стр. 449
^ Келлерер, Пферши и Писингер 2004, стр. 461
^ Келлерер, Пферши и Писингер 2004, стр. 465
^ Келлерер, Пферши и Писингер 2004, стр. 472
^ Фейерман, Мартин; Вайс, Харви (апрель 1973 г.). «Математическая модель программирования для построения тестов и оценки». Наука управления. 19 (8): 961–966. Дои:10.1287 / mnsc.19.8.961. JSTOR 2629127.
^ Писингер, Д. 2003. Где проблемы с твердым рюкзаком? Технический отчет 2003/08, Департамент компьютерных наук, Копенгагенский университет, Копенгаген, Дания.
^ Caccetta, L .; Куланут, А. (2001). «Вычислительные аспекты задач жесткого ранца». Нелинейный анализ. 47 (8): 5547–5558. Дои:10.1016 / s0362-546x (01) 00658-7.
^ ^а ^б ^c Пуарриес, Винсент; Янев, Никола; Андонов, Румен (2009). «Гибридный алгоритм решения неограниченной задачи о ранце». Дискретная оптимизация. 6 (1): 110–124. Дои:10.1016 / j.disopt.2008.09.004. ISSN 1572-5286.
^ Войтчак, Доминик (2018). «О сильной NP-полноте рациональных задач». Международный симпозиум по информатике в России. Конспект лекций по информатике. 10846: 308–320. arXiv:1802.09465. Дои:10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID 3637366.
^ ^а ^б Андонов, Румен; Пуарриес, Винсент; Раджопадхе, Санджай (2000). "Неограниченная проблема рюкзака: еще раз о динамическом программировании". Европейский журнал операционных исследований. 123 (2): 168–181. CiteSeerX 10.1.1.41.2135. Дои:10.1016 / S0377-2217 (99) 00265-9.^{[постоянная мертвая ссылка ]}
^ С. Мартелло, П. Тот, Проблемы с рюкзаком: алгоритмы и компьютерные реализации, Джон Уайли и сыновья, 1990
^ С. Мартелло, Д. Писингер, П. Тот, Динамическое программирование и строгие оценки для задачи о рюкзаке 0-1, Manag. Sci., 45:414–424, 1999.
^ Плато, G .; Элькихель, М. (1985). «Гибридный алгоритм для задачи о рюкзаке 0-1». Методы опер. Res. 49: 277–293.
^ Martello, S .; Тот, П. (1984). «Смесь динамического программирования и ветвей и границ для задачи суммы подмножества». Manag. Наука. 30 (6): 765–771. Дои:10.1287 / mnsc.30.6.765.
^ Горовиц, Эллис; Сахни, Сартадж (1974), "Вычисление разделов с приложениями к задаче о рюкзаке", Журнал Ассоциации вычислительной техники, 21 (2): 277–292, Дои:10.1145/321812.321823, HDL:1813/5989, МИСТЕР 0354006, S2CID 16866858
^ ^а ^б Вазирани, Виджай. Аппроксимационные алгоритмы. Springer-Verlag Berlin Heidelberg, 2003 г.
^ Данциг, Джордж Б. (1957). «Дискретно-переменные экстремальные задачи». Исследование операций. 5 (2): 266–288. Дои:10.1287 / opre.5.2.266.
^ Чанг, Т. Дж. И др. Эвристика для оптимизации портфеля с ограничением количества элементов.Технический отчет, Лондон SW7 2AZ, Англия: Школа менеджмента, ImperialCollege, май 1998 г.
^ Чанг, С.С. и др. "Оптимизация двух критериев на основе генетических алгоритмов для тяговых подстанций в железнодорожной системе постоянного тока. »В Fogel [102], 11-16.
^ Кулик, А .; Шахнаи, Х. (2010). «Для двухмерного рюкзака EPTAS не существует» (PDF). Инф. Процесс. Латыш. 110 (16): 707–712. CiteSeerX 10.1.1.161.5838. Дои:10.1016 / j.ipl.2010.05.031.
^ ^а ^б ^c Коэн Р. и Гребла Г. 2014. «Многомерное планирование OFDMA в беспроводной сети с релейными узлами». в Proc. IEEE INFOCOM’14, 2427–2435.
^ Ян Лан, Дьёрдь Доса, Синь Хан, Чэньян Чжоу, Аттила Бэнко [1]: 2D рюкзак: Упаковка квадратов, Теоретическая информатика Vol. 508. С. 35–40.
^ Чандра Чекури и Санджив Кханна (2005). «ПТАС для задачи о множественном рюкзаке». SIAM Журнал по вычислениям. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. Дои:10.1137 / s0097539700382820.
^ Wu, Z. Y .; Yang, Y.J .; Bai, F. S .; Мамедов М. (2011). «Условия глобальной оптимальности и методы оптимизации для квадратичных задач о ранце». Приложение J Optim Theory. 151 (2): 241–259. Дои:10.1007 / s10957-011-9885-4. S2CID 31208118.
^ Галло, G .; Hammer, P.L .; Симеоне, Б. (1980). Квадратичные задачи о ранце. Математическое программирование. 12. С. 132–149. Дои:10.1007 / BFb0120892. ISBN 978-3-642-00801-6.
^ Витцгалл, К. (1975). Математические методы выбора места для систем электронных сообщений (EMS). Внутренний отчет NBS. Bibcode:1975STIN ... 7618321W.
^ Ричард М. Карп (1972). "Сводимость среди комбинаторных задач ". В Р. Э. Миллер и Дж. У. Тэтчер (редакторы). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103
^ Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (2000). "Проблема суммы множественных подмножеств". СИАМ Дж. Оптим. 11 (2): 308–319. CiteSeerX 10.1.1.21.9826. Дои:10.1137 / S1052623498348481.

внешняя ссылка

Бесплатная загрузка книги Сильвано Мартелло и Паоло Тота "Задачи о ранце: алгоритмы и компьютерные реализации"
Слайды лекции по задаче о рюкзаке
PYAsUKP: еще один решатель проблемы неограниченного рюкзака, с кодом, использующим отношения доминирования в гибридном алгоритме, тестами и загружаемыми копиями некоторых статей.
Домашняя страница Давида Писингера с загружаемыми копиями некоторых статей из списка публикаций (в том числе «Где проблемы с рюкзаком?»)
Решение проблем с рюкзаком на многих языках в Код Розетты
Алгоритм динамического программирования для задачи о рюкзаке 0/1
Решение проблем с рюкзаком (онлайн)
Решение 0-1-KNAPSACK с помощью генетических алгоритмов на Ruby
Коды для квадратичной задачи о ранце

[1] Мэтьюз, Г. Б. (25 июня 1897 г.). «О разделении чисел» (PDF). Труды Лондонского математического общества. 28: 486–490. Дои:10.1112 / плмс / с1-28.1.486.

[2] Данциг, Тобиас. Числа: язык науки, 1930.

[3] Скиена, С. С. (сентябрь 1999 г.). «Кто интересуется алгоритмами и почему? Уроки из репозитория алгоритмов Стоуни-Брук». Новости ACM SIGACT. 30 (3): 65–74. CiteSeerX 10.1.1.41.8357. Дои:10.1145/333623.333627. ISSN 0163-5700. S2CID 15619060.

[4] Келлерер, Пферши и Писингер 2004, стр. 449

[5] Келлерер, Пферши и Писингер 2004, стр. 461

[6] Келлерер, Пферши и Писингер 2004, стр. 465

[7] Келлерер, Пферши и Писингер 2004, стр. 472

[8] Фейерман, Мартин; Вайс, Харви (апрель 1973 г.). «Математическая модель программирования для построения тестов и оценки». Наука управления. 19 (8): 961–966. Дои:10.1287 / mnsc.19.8.961. JSTOR 2629127.

[pisinger200308-9] Писингер, Д. 2003. Где проблемы с твердым рюкзаком? Технический отчет 2003/08, Департамент компьютерных наук, Копенгагенский университет, Копенгаген, Дания.

[Cacetta2001-10] Caccetta, L .; Куланут, А. (2001). «Вычислительные аспекты задач жесткого ранца». Нелинейный анализ. 47 (8): 5547–5558. Дои:10.1016 / s0362-546x (01) 00658-7.

[poirriez_et_all_2009-11] а ^б ^c Пуарриес, Винсент; Янев, Никола; Андонов, Румен (2009). «Гибридный алгоритм решения неограниченной задачи о ранце». Дискретная оптимизация. 6 (1): 110–124. Дои:10.1016 / j.disopt.2008.09.004. ISSN 1572-5286.

[Wojtczak18-12] Войтчак, Доминик (2018). «О сильной NP-полноте рациональных задач». Международный симпозиум по информатике в России. Конспект лекций по информатике. 10846: 308–320. arXiv:1802.09465. Дои:10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID 3637366.

[eduk2000-13] а ^б Андонов, Румен; Пуарриес, Винсент; Раджопадхе, Санджай (2000). "Неограниченная проблема рюкзака: еще раз о динамическом программировании". Европейский журнал операционных исследований. 123 (2): 168–181. CiteSeerX 10.1.1.41.2135. Дои:10.1016 / S0377-2217 (99) 00265-9.^{[постоянная мертвая ссылка ]}

[martellototh90-14] С. Мартелло, П. Тот, Проблемы с рюкзаком: алгоритмы и компьютерные реализации, Джон Уайли и сыновья, 1990

[martellopisingertoth99a-15] С. Мартелло, Д. Писингер, П. Тот, Динамическое программирование и строгие оценки для задачи о рюкзаке 0-1, Manag. Sci., 45:414–424, 1999.

[plateau85-16] Плато, G .; Элькихель, М. (1985). «Гибридный алгоритм для задачи о рюкзаке 0-1». Методы опер. Res. 49: 277–293.

[martellotothe99-17] Martello, S .; Тот, П. (1984). «Смесь динамического программирования и ветвей и границ для задачи суммы подмножества». Manag. Наука. 30 (6): 765–771. Дои:10.1287 / mnsc.30.6.765.

[18] Горовиц, Эллис; Сахни, Сартадж (1974), "Вычисление разделов с приложениями к задаче о рюкзаке", Журнал Ассоциации вычислительной техники, 21 (2): 277–292, Дои:10.1145/321812.321823, HDL:1813/5989, МИСТЕР 0354006, S2CID 16866858

[Vazirani,_Vijay_2003-19] а ^б Вазирани, Виджай. Аппроксимационные алгоритмы. Springer-Verlag Berlin Heidelberg, 2003 г.

[dantzig1957-20] Данциг, Джордж Б. (1957). «Дискретно-переменные экстремальные задачи». Исследование операций. 5 (2): 266–288. Дои:10.1287 / opre.5.2.266.

[21] Чанг, Т. Дж. И др. Эвристика для оптимизации портфеля с ограничением количества элементов.Технический отчет, Лондон SW7 2AZ, Англия: Школа менеджмента, ImperialCollege, май 1998 г.

[22] Чанг, С.С. и др. "Оптимизация двух критериев на основе генетических алгоритмов для тяговых подстанций в железнодорожной системе постоянного тока. »В Fogel [102], 11-16.

[23] Кулик, А .; Шахнаи, Х. (2010). «Для двухмерного рюкзака EPTAS не существует» (PDF). Инф. Процесс. Латыш. 110 (16): 707–712. CiteSeerX 10.1.1.161.5838. Дои:10.1016 / j.ipl.2010.05.031.

[CohenGrebla-24] а ^б ^c Коэн Р. и Гребла Г. 2014. «Многомерное планирование OFDMA в беспроводной сети с релейными узлами». в Proc. IEEE INFOCOM’14, 2427–2435.

[25] Ян Лан, Дьёрдь Доса, Синь Хан, Чэньян Чжоу, Аттила Бэнко [1]: 2D рюкзак: Упаковка квадратов, Теоретическая информатика Vol. 508. С. 35–40.

[26] Чандра Чекури и Санджив Кханна (2005). «ПТАС для задачи о множественном рюкзаке». SIAM Журнал по вычислениям. 35 (3): 713–728. CiteSeerX 10.1.1.226.3387. Дои:10.1137 / s0097539700382820.

[QKP-27] Wu, Z. Y .; Yang, Y.J .; Bai, F. S .; Мамедов М. (2011). «Условия глобальной оптимальности и методы оптимизации для квадратичных задач о ранце». Приложение J Optim Theory. 151 (2): 241–259. Дои:10.1007 / s10957-011-9885-4. S2CID 31208118.

[28] Галло, G .; Hammer, P.L .; Симеоне, Б. (1980). Квадратичные задачи о ранце. Математическое программирование. 12. С. 132–149. Дои:10.1007 / BFb0120892. ISBN 978-3-642-00801-6.

[29] Витцгалл, К. (1975). Математические методы выбора места для систем электронных сообщений (EMS). Внутренний отчет NBS. Bibcode:1975STIN ... 7618321W.

[30] Ричард М. Карп (1972). "Сводимость среди комбинаторных задач ". В Р. Э. Миллер и Дж. У. Тэтчер (редакторы). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103

[31] Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (2000). "Проблема суммы множественных подмножеств". СИАМ Дж. Оптим. 11 (2): 308–319. CiteSeerX 10.1.1.21.9826. Дои:10.1137 / S1052623498348481.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Задача о рюкзаке - Knapsack problem

Содержание

Приложения

Определение

Вычислительная сложность

Решение

Алгоритм предварительного динамического программирования

0-1 задача о ранце

Встреча посередине

Алгоритмы аппроксимации

Алгоритм жадного приближения

Схема аппроксимации полностью полиномиальным временем

Отношения доминирования

Вариации

Задача о многоцелевом рюкзаке

Многомерная задача о рюкзаке

Задача с несколькими рюкзаками

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

Проблема подмножества суммы

Смотрите также

Примечания

Рекомендации

внешняя ссылка