Задача о рюкзаке

Задача комбинаторной оптимизации

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

Задача о рюкзаке — это следующая задача комбинаторной оптимизации :

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

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

Задача о рюкзаке изучается уже более века, первые работы датируются 1897 годом. ^[1]

Приложения

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

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

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

Определение

Наиболее распространенной решаемой проблемой является задача о рюкзаке 0-1 , которая ограничивает количество копий каждого вида предметов нулем или одним. Дан набор предметов, пронумерованных от 1 до , каждый из которых имеет вес и ценность , а также максимальную грузоподъемность , ${\displaystyle x_{i}}$ ${\displaystyle n}$ ${\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}\in \{0,1\}}$

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

Задача о рюкзаке с ограничением ( BKP ) снимает ограничение, что существует только один экземпляр каждого предмета, но ограничивает количество копий каждого вида предметов максимальным неотрицательным целым значением : ${\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\}.}$

Задача о неограниченном рюкзаке ( UKP ) не устанавливает верхней границы для количества копий каждого вида предметов и может быть сформулирована так же, как и выше, за исключением того, что единственным ограничением является то, что это должно быть неотрицательное целое число. ${\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}\in \mathbb {Z} ,\ x_{i}\geq 0.}$

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

Сложность вычислений

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

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

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

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

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

Модели удельной стоимости

NP-трудность задачи о ранце относится к вычислительным моделям, в которых размер целых чисел имеет значение (например, машина Тьюринга ). Напротив, деревья решений считают каждое решение одним шагом. Добкин и Липтон ^[12] показывают нижнюю границу для линейных деревьев решений для задачи о ранце, то есть деревьев, где узлы решений проверяют знак аффинных функций . ^[13] Это было обобщено на алгебраические деревья решений Стилом и Яо. ^[14] Если элементы в задаче являются действительными числами или рациональными числами , нижняя граница дерева решений распространяется на модель реальной машины с произвольным доступом с набором инструкций, который включает сложение, вычитание и умножение действительных чисел, а также сравнение и либо деление, либо получение остатка («пол»). ^[15] Эта модель охватывает больше алгоритмов, чем модель алгебраического дерева решений, поскольку она охватывает алгоритмы, которые используют индексацию в таблицах. Однако в этой модели учитываются все шаги программы, а не только решения. Верхняя граница для модели дерева решений была дана Мейером ауф дер Хайде ^[16] , который показал, что для каждого n существует линейное дерево решений глубиной O ( n ⁴ ) , которое решает задачу подмножества-суммы с n элементами. Обратите внимание, что это не подразумевает никакой верхней границы для алгоритма, который должен решать задачу для любого заданного n . ${\displaystyle {1 \over 2}n^{2}}$

Решение

Существует несколько алгоритмов для решения задач о рюкзаке, основанных на подходе динамического программирования ^[17] , подходе ветвей и границ ^[18] или гибридизации обоих подходов. ^{[10] [19] [20] [21]}

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

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

${\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)}$

при условии и ${\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_{n}+m[w-w_{n}])}$ ${\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 , сложность не противоречит тому факту, что задача о ранце является NP-полной , поскольку , в отличие от , не является полиномиальной по длине входа в задачу. Длина входа в задачу пропорциональна количеству бит в , , а не самой себе. Однако, поскольку это время выполнения является псевдополиномиальным , это делает (версию решения) задачи о ранце слабо NP-полной задачей . ${\displaystyle O(nW)}$ ${\displaystyle W}$ ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle \log W}$ ${\displaystyle W}$

0-1 задача о рюкзаке

Демонстрация подхода динамического программирования.

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

Мы можем определить рекурсивно следующим образом: (Определение A) ${\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]}$

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

// Вход:// Значения (хранятся в массиве v)// Веса (хранятся в массиве w)// Количество отдельных элементов (n)// Емкость рюкзака (Вт)// ПРИМЕЧАНИЕ: Предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1.массив m [ 0. . n , 0. . W ];  для j от 0 до W сделать :       м [ 0 , j ] := 0   для i от 1 до n сделать :       м [ я , 0 ] := 0   для i от 1 до n сделать :       для j от 1 до W сделать :       если w [ i ] > j тогда :     m [ i , j ] := m [ i -1 , j ]     еще : m [ i , j ] := max ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])        

Следовательно, это решение будет выполняться во времени и пространстве. (Если нам нужно только значение m[n,W], мы можем изменить код так, чтобы требуемый объем памяти составлял O(W), что позволяет хранить две последние строки массива «m».) ${\displaystyle O(nW)}$ ${\displaystyle O(nW)}$

Однако если мы сделаем шаг или два дальше, мы должны знать, что метод будет работать в промежутке времени между и . Из определения A мы знаем, что нет необходимости вычислять все веса, когда количество элементов и сами элементы, которые мы выбрали, фиксированы. То есть, программа выше вычисляет больше, чем необходимо, потому что вес часто меняется от 0 до W. С этой точки зрения мы можем запрограммировать этот метод так, чтобы он работал рекурсивно. ${\displaystyle O(nW)}$ ${\displaystyle O(2^{n})}$

// Вход:// Значения (хранятся в массиве v)// Веса (хранятся в массиве w)// Количество отдельных элементов (n)// Емкость рюкзака (Вт)// ПРИМЕЧАНИЕ: Предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1.Определить значение [ n , W ]  Инициализируем все значения [ i , j ] = -1     Определить m := ( i , j ) // Определить функцию m так, чтобы она представляла максимальное значение, которое мы можем получить при условии: использовать первые i элементов, общий предел веса равен j  { если i == 0 или j <= 0, то :         значение [ i , j ] = 0    возвращаться если ( значение [ i -1 , j ] == -1 ) тогда : // m[i-1, j] не было вычислено, мы должны вызвать функцию m       м ( я -1 , j )  если w [ i ] > j тогда : // предмет не может поместиться в сумку      значение [ i , j ] = значение [ i -1 , j ]     еще :  если ( значение [ i -1 , j - w [ i ]] == -1 ) тогда : // m[i-1,jw[i]] не было вычислено, мы должны вызвать функцию m       м ( я -1 , дж - ш [ я ])  значение [ i , j ] = макс ( значение [ i -1 , j ], значение [ i -1 , j - w [ i ]] + v [ i ])       }Выполнить m ( n , W )  

Например, есть 10 различных предметов, а предел веса составляет 67. Таким образом, если вы используете описанный выше метод для вычисления , вы получите это, за исключением вызовов, которые производят : $${\displaystyle {\begin{aligned}&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{aligned}}}$$ ${\displaystyle m(10,67)}$ ${\displaystyle m(i,j)=0}$ $${\displaystyle {\begin{aligned}&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,m(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,m(1,23)=505\\\end{aligned}}}$$

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

Чтобы найти фактическое подмножество элементов, а не только их общую стоимость, мы можем выполнить это после запуска функции выше:

/*** Возвращает индексы предметов оптимального рюкзака.* i: Мы можем включить предметы с 1 по i в рюкзак* j: максимальный вес рюкзака*/функция рюкзак ( i : int , j : int ) : Установить <int> {​​       если я == 0 тогда :     возвращаться {}  если m [ i , j ] > m [ i -1 , j ] тогда :       возврат { i } ∪ рюкзак ( i -1 , j - w [ i ])     еще : возвратный рюкзак ( i -1 , j )  }рюкзак ( н , В ) 

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

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

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

Алгоритм занимает место, и эффективные реализации шага 3 (например, сортировка подмножеств B по весу, отбрасывание подмножеств B, которые весят больше, чем другие подмножества B с большим или равным значением, и использование бинарного поиска для поиска наилучшего соответствия) приводят к времени выполнения . Как и в случае с атакой meet in the middle в криптографии, это улучшает время выполнения наивного подхода грубой силы (исследование всех подмножеств ), за счет использования экспоненциального, а не постоянного пространства (см. также baby-step giant-step ). Текущее усовершенствование алгоритма meet-in-the-middle, использующее идеи из алгоритма Шреппеля и Шамира для суммы подмножества, предоставляет в качестве следствия рандомизированный алгоритм для Knapsack, который сохраняет (с точностью до полиномиальных множителей) время выполнения и снижает требования к пространству до (см. ^[23] Следствие 1.4). Напротив, самый известный детерминированный алгоритм работает со временем с немного худшей пространственной сложностью . ^[24] ${\displaystyle O(2^{n/2})}$ ${\displaystyle O(n2^{n/2})}$ ${\displaystyle O(n2^{n})}$ ${\displaystyle \{1...n\}}$ ${\displaystyle O^{*}(2^{n/2})}$ ${\displaystyle O^{*}(2^{0.249999n})}$ ${\displaystyle O^{*}(2^{n/2})}$ ${\displaystyle O^{*}(2^{n/4})}$

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

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

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

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

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

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

Можно показать, что средняя производительность сходится к оптимальному решению по распределению с частотой ошибок ^[27] ${\displaystyle n^{-1/2}}$

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

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

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

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

Квантовая приближенная оптимизация

Квантовый приближенный алгоритм оптимизации (QAOA) может быть использован для решения задачи о ранце с использованием квантовых вычислений путем минимизации гамильтониана задачи. Гамильтониан ранца строится путем вложения условия ограничения в функцию стоимости задачи со штрафным членом. ^[28] где — константа штрафа, которая определяется путем тонкой настройки для конкретного случая. $${\displaystyle {H}=-\sum _{i=1}^{n}v_{i}x_{i}+P\left(\sum _{i=1}^{n}w_{i}x_{i}-W\right)^{2},}$$ ${\displaystyle P}$

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

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

Нахождение отношений доминирования позволяет нам значительно сократить размер пространства поиска. Существует несколько различных типов отношений доминирования, ^[10] которые все удовлетворяют неравенству вида:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$, а для некоторых ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ ${\displaystyle x\in Z_{+}^{n}}$

где и . Вектор обозначает количество копий каждого члена . ${\displaystyle \alpha \in Z_{+}\,,J\subsetneq N}$ ${\displaystyle i\not \in J}$ ${\displaystyle x}$ ${\displaystyle J}$

Коллективное господство

-й элемент коллективно доминируется , записывается как , если общий вес некоторой комбинации элементов в меньше w _i , а их общее значение больше v _i . Формально, и для некоторых , то есть . Проверка этого доминирования является вычислительно сложной, поэтому ее можно использовать только с подходом динамического программирования. Фактически, это эквивалентно решению меньшей задачи принятия решения о рюкзаке, где , , и элементы ограничены . ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i\ll J}$ ${\displaystyle J}$ ${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$ ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$ ${\displaystyle x\in Z_{+}^{n}}$ ${\displaystyle \alpha =1}$ ${\displaystyle V=v_{i}}$ ${\displaystyle W=w_{i}}$ ${\displaystyle J}$

Доминирование порога

-й элемент порогово доминируется , записывается как , если некоторое количество копий доминируется . Формально, , и для некоторых и . Это обобщение коллективного доминирования, впервые введенное в ^[17] и использованное в алгоритме EDUK. Наименьшее из таких определяет порог элемента , записывается . В этом случае оптимальное решение может содержать не более копий . ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i\prec \prec J}$ ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$ ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ ${\displaystyle x\in Z_{+}^{n}}$ ${\displaystyle \alpha \geq 1}$ ${\displaystyle \alpha }$ ${\displaystyle i}$ ${\displaystyle t_{i}=(\alpha -1)w_{i}}$ ${\displaystyle \alpha -1}$ ${\displaystyle i}$

Множественное доминирование

-й элемент многократно доминируется одним элементом , что записывается как , если доминируется некоторым количеством копий . Формально, , и для некоторых ie . Это доминирование можно эффективно использовать во время предварительной обработки, поскольку его можно обнаружить относительно легко. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i\ll _{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}}}\rfloor }$

Модульное доминирование

Пусть будет лучшим элементом , то есть для всех . Это элемент с наибольшей плотностью значения. -й элемент модульно доминируется одним элементом , записывается как , если доминируется плюс несколько копий . Формально, , и , то есть . ${\displaystyle b}$ ${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i\ll _{\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}$

Вариации

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

Многокритериальная задача о рюкзаке

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

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

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

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

Многомерный рюкзак вычислительно сложнее, чем рюкзак; даже для задача не имеет EPTAS , если только P NP. ^[31] Однако показано, что алгоритм в ^[32] эффективно решает разреженные экземпляры. Экземпляр многомерного рюкзака является разреженным, если существует набор для такой, что для каждого элемента рюкзака , такой, что и . Такие экземпляры возникают, например, при планировании пакетов в беспроводной сети с ретрансляционными узлами. ^[32] Алгоритм из ^[32] также решает разреженные экземпляры варианта с множественным выбором, многомерного рюкзака с множественным выбором. ${\displaystyle D=2}$ ${\displaystyle =}$ ${\displaystyle J=\{1,2,\ldots ,m\}}$ ${\displaystyle m<D}$ ${\displaystyle i}$ ${\displaystyle \exists z>m}$ ${\displaystyle \forall j\in J\cup \{z\},\ w_{ij}\geq 0}$ ${\displaystyle \forall y\notin J\cup \{z\},w_{iy}=0}$

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

Задача о множественном рюкзаке

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

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

Квадратичная задача о рюкзаке максимизирует квадратичную целевую функцию с учетом бинарных и линейных ограничений по емкости. ^[35] Задача была представлена ​​Галло, Хаммером и Симеоне в 1980 году, ^[36] однако первое рассмотрение задачи относится к Вицгаллу в 1975 году. ^[37]

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

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

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

Геометрическая задача о рюкзаке

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

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

• Портал компьютерного программирования

• Задача упаковки контейнеров  – Математическая и вычислительная задача
• Проблема сдачи  — выбор наименьшего количества монет для получения заданной суммы денег
• Комбинаторный аукцион  – интеллектуальный рынок, на котором участники могут делать ставки на комбинации дискретных товаров, а не на отдельные товары или непрерывные количества.Pages displaying wikidata descriptions as a fallback
• Комбинаторная оптимизация  – Подраздел математической оптимизации
• Задача о непрерывном рюкзаке
• Задача о раскрое запасов  – Математическая задача в исследовании операций
• Аукцион по продаже рюкзаков
• Список задач о рюкзаке
• Задача упаковки  – задачи, в которых необходимо найти наиболее эффективный способ упаковки объектов в контейнеры.Pages displaying short descriptions of redirect targets

Примечания

1. Мэтьюз, ГБ (25 июня 1897 г.). «О разделении чисел» (PDF) . Труды Лондонского математического общества . 28 : 486–490. doi :10.1112/plms/s1-28.1.486.
2. Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком. Берлин: Шпрингер. п. 449. ИСБН 978-3-540-40286-2. Получено 5 мая 2022 г. .
3. Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком. Берлин: Шпрингер. п. 461. ИСБН 978-3-540-40286-2. Получено 5 мая 2022 г. .
4. Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком. Берлин: Шпрингер. п. 465. ИСБН 978-3-540-40286-2. Получено 5 мая 2022 г. .
5. Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком. Берлин: Шпрингер. п. 472. ИСБН 978-3-540-40286-2. Получено 5 мая 2022 г. .
6. Фейерман, Мартин; Вайс, Харви (апрель 1973 г.). «Математическая модель программирования для построения и оценки тестов». Management Science . 19 (8): 961–966. doi :10.1287/mnsc.19.8.961. JSTOR  2629127.
7. Скиена, СС (сентябрь 1999 г.). «Кто интересуется алгоритмами и почему? Уроки из репозитория алгоритмов Стоуни-Брук». ACM SIGACT News . 30 (3): 65–74. CiteSeerX 10.1.1.41.8357 . doi :10.1145/333623.333627. ISSN  0163-5700. S2CID  15619060. 
8. Писингер, Д. 2003. Где трудные задачи о рюкзаке? Технический отчет 2003/08, Кафедра компьютерных наук, Копенгагенский университет, Копенгаген, Дания.
9. Caccetta, L.; Kulanoot, A. (2001). «Вычислительные аспекты сложных задач о ранце». Нелинейный анализ . 47 (8): 5547–5558. doi :10.1016/s0362-546x(01)00658-7.
10. Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). "Гибридный алгоритм для задачи о неограниченном рюкзаке". Discrete Optimization . 6 (1): 110–124. doi : 10.1016/j.disopt.2008.09.004 . ISSN  1572-5286. S2CID  8820628.
11. Wojtczak, Dominik (2018). «О сильной NP-полноте рациональных задач». Computer Science – Theory and Applications . Lecture Notes in Computer Science. Vol. 10846. pp. 308–320. arXiv : 1802.09465 . doi :10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID  3637366.
12. Добкин, Дэвид; Липтон, Ричард Дж. (1978). «Нижняя граница ½n2 для линейных программ поиска для задачи о ранце». Журнал компьютерных и системных наук . 16 (3): 413–417. doi :10.1016/0022-0000(78)90026-0.
13. Фактически, нижняя граница применима к задаче о сумме подмножеств, которая является частным случаем задачи о ранце.
14. Майкл Стил, Дж.; Яо, Эндрю К. (1 марта 1982 г.). «Нижние границы для алгебраических деревьев решений». Журнал алгоритмов . 3 (1): 1–8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
15. Бен-Амрам, Амир М.; Галил, Цви (2001), «Топологические нижние границы алгебраических машин с произвольным доступом», SIAM Journal on Computing , 31 (3): 722–761, doi :10.1137/S0097539797329397.
16. auf der Heide, Meyer (1984), "Полиномиальный линейный алгоритм поиска для n -мерной задачи о ранце", Journal of the ACM , 31 (3): 668–676, doi :10.1145/828.322450
17. Андонов, Румен; Пуарье, Винсент; Раджопадхье, Санджай (2000). «Неограниченная задача о рюкзаке: пересмотр динамического программирования». Европейский журнал исследований операций . 123 (2): 168–181. CiteSeerX 10.1.1.41.2135 . doi :10.1016/S0377-2217(99)00265-9. 
18. С. Мартелло, П. Тот, Задачи о рюкзаке: алгоритмы и компьютерные реализации, John Wiley and Sons, 1990
19. С. Мартелло, Д. Писингер, П. Тот, Динамическое программирование и сильные оценки для задачи о рюкзаке 0-1, Manag. Sci. , 45:414–424, 1999.
20. Plateau, G.; Elkihel, M. (1985). «Гибридный алгоритм для задачи о рюкзаке 0-1». Methods of Oper. Res . 49 : 277–293.
21. Мартелло, С.; Тот, П. (1984). «Смесь динамического программирования и метода ветвей и границ для задачи подмножества-суммы». Manag. Sci . 30 (6): 765–771. doi :10.1287/mnsc.30.6.765.
22. Хоровиц, Эллис; Сахни, Сартай (1974), «Вычислительные разбиения с приложениями к задаче о ранце», Журнал Ассоциации вычислительной техники , 21 (2): 277–292, doi : 10.1145/321812.321823, hdl : 1813/5989 , MR  0354006, S2CID  16866858
23. Недерлоф, Йеспер; Венгжицкий, Кароль (12 апреля 2021 г.). «Улучшение алгоритма Шрёппеля и Шамира для вычисления суммы подмножества с помощью ортогональных векторов». arXiv : 2010.08576 [cs.DS].
24. Шрёппель, Ричард; Шамир, Ади (август 1981 г.). «Алгоритм $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ для некоторых NP-полных задач». Журнал SIAM по вычислениям . 10 (3): 456–464. doi :10.1137/0210033. ISSN  0097-5397.
25. Вазирани, Виджай. Алгоритмы аппроксимации. Springer-Verlag Берлин Гейдельберг, 2003 г.
26. Данциг, Джордж Б. (1957). «Дискретно-переменные экстремальные задачи». Исследование операций . 5 (2): 266–288. doi :10.1287/opre.5.2.266.
27. Кэлвин, Джеймс М.; Леунг, Джозеф Й. -Т. (1 мая 2003 г.). «Анализ среднего случая жадного алгоритма для задачи о рюкзаке 0/1». Operations Research Letters . 31 (3): 202–210. doi :10.1016/S0167-6377(02)00222-5.
28. Лукас, Эндрю (2014). «Изинговские формулировки многих NP-задач». Frontiers in Physics . 2 : 5. arXiv : 1302.5843 . Bibcode : 2014FrP.....2....5L. doi : 10.3389/fphy.2014.00005 . ISSN  2296-424X.
29. Чанг, Т.Дж. и др. Эвристика для оптимизации портфеля с ограничениями по мощности. Технический отчет, Лондон SW7 2AZ, Англия: Школа менеджмента, Имперский колледж, май 1998 г.
30. Чанг, К.С. и др. «Бикритериальная оптимизация на основе генетического алгоритма для тяговых подстанций в системе железных дорог постоянного тока». В Fogel [102], 11-16.
31. Кулик, А.; Шачнай, Х. (2010). «Для двумерного рюкзака нет EPTAS» (PDF) . Inf. Process. Lett . 110 (16): 707–712. CiteSeerX 10.1.1.161.5838 . doi :10.1016/j.ipl.2010.05.031. 
32. Коэн, Р. и Гребла, Г. 2014. «Многомерное планирование OFDMA в беспроводной сети с релейными узлами». в Proc. IEEE INFOCOM'14 , 2427–2435.
33. Ян Лан, Дьёрдь Доса, Синь Хан, Чэньян Чжоу, Аттила Бенко [1]: 2D-рюкзак: Упаковка квадратов , Теоретическая информатика Том. 508, стр. 35–40.
34. Чандра Чекури и Санджив Кханна (2005). «PTAS для задачи о множественном рюкзаке». SIAM Journal on Computing . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi :10.1137/s0097539700382820. 
35. Wu, ZY; Yang, YJ; Bai, FS; Mammadov, M. (2011). «Условия глобальной оптимальности и методы оптимизации для квадратичных задач о ранце». J Optim Theory Appl . 151 (2): 241–259. doi :10.1007/s10957-011-9885-4. S2CID  31208118.
36. Галло, Г.; Хаммер, ПЛ; Симеоне, Б. (1980). "Квадратичные задачи о ранце". Комбинаторная оптимизация . Исследования по математическому программированию. Том 12. С. 132–149. doi :10.1007/BFb0120892. ISBN 978-3-642-00801-6.
37. Witzgall, C. (1975). "Математические методы выбора места для систем электронных сообщений (EMS)". Технический отчет NASA Sti/Recon № 76. Внутренний отчет NBS: 18321. Bibcode : 1975STIN...7618321W.
38. Ричард М. Карп (1972). «Сводимость среди комбинаторных проблем». В RE Miller и JW Thatcher (редакторы). Сложность компьютерных вычислений. Нью-Йорк: Пленум. С. 85–103
39. Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (2000). «Проблема суммы множественных подмножеств». SIAM J. Optim . 11 (2): 308–319. CiteSeerX 10.1.1.21.9826 . doi :10.1137/S1052623498348481. 
40. Гальвес, Вальдо; Грандони, Фабрицио; Ингала, Сальваторе; Гейдрих, Сэнди; Хан, Ариндам; Визе, Андреас (2021). «Аппроксимация геометрического рюкзака с помощью L-упаковок». ACM Trans. Алгоритмы . 17 (4): 33:1–33:67. arXiv : 1711.07710 . doi : 10.1145/3473713.

Ссылки

• Гари, Майкл Р.; Дэвид С. Джонсон (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman. ISBN 978-0-7167-1045-5.А6: MP9, стр.247.
• Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком . Спрингер. дои : 10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. MR  2161720. S2CID  28836720.
• Мартелло, Сильвано; Тот, Паоло (1990). Задачи о рюкзаке: алгоритмы и компьютерные реализации. Wiley-Interscience. ISBN 978-0-471-92420-3. МР  1086874.

Внешние ссылки

• Слайды лекции по задаче о рюкзаке
• PYAsUKP: Еще один решатель задачи о неограниченном рюкзаке с кодом, использующим преимущества отношений доминирования в гибридном алгоритме, бенчмарками и загружаемыми копиями некоторых статей.
• Домашняя страница Дэвида Писингера с доступными для скачивания копиями некоторых статей из списка публикаций (включая «Где находятся сложные задачи о рюкзаке?»)
• Решения задач о рюкзаке на многих языках на Rosetta Code
• Алгоритм динамического программирования для задачи о рюкзаке 0/1
• Решатель задач о рюкзаке (онлайн)
• Решение задачи 0-1-KNAPSACK с помощью генетических алгоритмов в Ruby Архивировано 23 мая 2011 г. на Wayback Machine
• Коды для квадратной задачи о ранце Архивировано 14 февраля 2015 г. на Wayback Machine

• Оптимизация трехмерной упаковки контейнеров
• Решение целочисленного программирования Knapsack на Python Gekko (программное обеспечение для оптимизации)