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

Проблема комбинаторной оптимизации

Пример одномерной (с ограничениями) задачи о рюкзаке: какие книги следует выбрать, чтобы максимизировать количество денег, сохраняя при этом общий вес не более 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 ). Эта задача является ко-NP-полной .
• Существует псевдополиномиальный алгоритм времени, использующий динамическое программирование .
• Существует полностью полиномиальная схема аппроксимации , которая использует в качестве подпрограммы алгоритм псевдополиномиального времени, описанный ниже.
• Тем не менее, многие случаи, возникающие на практике, и «случайные случаи» из некоторых дистрибутивов могут быть решены точно.

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

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

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

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

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

Решение

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

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

Задача о неограниченном рюкзаке ( 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]}$if (новый предмет превышает текущий предел веса) ${\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.массив м [ 0. . н , 0. . В ];  для j от 0 до W сделайте :       м [ 0 , j ] := 0   для я от 1 до n сделайте :       м [ я , 0 ] := 0   для я от 1 до n сделайте :       для j от 1 до W сделайте :       если w [ i ] > j , то :     м [ я , j ] := м [ я -1 , j ]     еще : м [ я , j ] := max ( м [ я -1 , j ], м [ я -1 , j - ш [ я ]] + v [ я ])        

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

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

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

Например, существует 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 ) : Set < int > {       если я == 0 , то :     возвращаться {}  если m [ i , j ] > m [ i -1 , j ] тогда :       вернуть { я } ∪ рюкзак ( я -1 , j - ш [ я ])     еще : вернуть рюкзак ( i -1 , j )  }рюкзак ( n , W ) 

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

Другой алгоритм для ранца 0-1, открытый в 1974 году ^[24] и иногда называемый «встреча посередине» из-за параллелей с алгоритмом с аналогичным названием в криптографии , является экспоненциальным по количеству различных элементов, но может быть предпочтительнее алгоритм 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 большего или равного значения, и использование двоичного поиска для поиска наилучшего соответствия) ) приводит к времени выполнения . Как и в случае с атакой «встреча посередине» в криптографии, это улучшает время выполнения наивного подхода грубой силы (исследуя все подмножества ) за счет использования экспоненциального, а не постоянного пространства (см. также baby-step-giant-step ). Современное усовершенствование алгоритма «встреча посередине», использующее идеи алгоритма Шреппеля и Шамира для суммы подмножества, обеспечивает в качестве следствия рандомизированный алгоритм для Knapsack, который сохраняет время работы (с точностью до полиномиальных коэффициентов) и сводит требования к пространству до (см. ^[25, следствие 1.4]). Напротив, самый известный детерминированный алгоритм работает по времени с несколько худшей пространственной сложностью . ^[26] ${\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-сложная, представляет собой один из наборов алгоритмов, которые все же можно аппроксимировать в любой заданной степени. Это означает, что задача имеет полиномиальную схему аппроксимации. Точнее, задача о рюкзаке имеет полностью полиномиальную схему аппроксимации (FPTAS). ^[27]

Жадный алгоритм аппроксимации

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

Для ограниченной задачи, где предложение каждого вида предметов ограничено, приведенный выше алгоритм может быть далек от оптимального. Тем не менее, простая модификация позволяет нам решить этот случай: предположим для простоты, что все предметы по отдельности помещаются в мешок ( для всех ). Найдите решение , жадно упаковывая предметы как можно дольше, т. е. туда, где . Кроме того, создайте второе решение , содержащее первый элемент, который не подошел. Поскольку обеспечивает верхнюю границу для ЛП-релаксации задачи, один из наборов должен иметь значение не менее ; таким образом, мы возвращаем то из значений , которое имеет лучшее значение для получения -аппроксимации . ${\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}$

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

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

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

на вход  алгоритма 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 do  := end for ${\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) можно использовать для решения задачи о рюкзаке с использованием квантовых вычислений путем минимизации гамильтониана задачи. Гамильтониан Ранца строится путем включения условия ограничения в функцию стоимости задачи со штрафным членом ^[30] .

$${\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}$

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

${\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}$

Коллективное доминирование

-th предмет коллективно доминирует , записывается как , если _общий вес некоторой комбинации предметов в меньше, чем wi , а их общая стоимость больше, _чем vi . Формально и для некоторых , т.е. Проверка этого доминирования сложна с вычислительной точки зрения, поэтому ее можно использовать только с помощью подхода динамического программирования. Фактически, это эквивалентно решению меньшей задачи о рюкзаке, где , и предметы ограничены . ${\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}$

Пороговое доминирование

-й элемент является пороговым значением , в котором доминирует , и записывается как , если некоторое количество копий доминирует . Формально , ​​а для некоторых и . Это обобщение коллективного доминирования, впервые введенное в ^[19] и использованное в алгоритме 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}$

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

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

Вариации

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

Многоцелевая задача о рюкзаке

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

В качестве примера предположим, что вы управляете круизным лайнером. Вам предстоит решить, сколько известных комиков нанять. Эта лодка может вместить не более одной тонны пассажиров, а артисты должны весить менее 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}}$

Многомерный рюкзак сложнее в вычислительном отношении, чем рюкзак; даже для ЭПТАС , проблемы нет, разве что П НП. ^[33] Однако показано , что алгоритм в ^[34] эффективно решает редкие экземпляры. Экземпляр многомерного рюкзака является разреженным, если существует набор для такого, что для каждого предмета рюкзака , такого что и . Такие случаи возникают, например, при планировании пакетов в беспроводной сети с узлами ретрансляции. ^[34] Алгоритм из ^[34] также решает редкие случаи варианта с множественным выбором, многомерного рюкзака с множественным выбором. ${\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 (полка увеличения высоты) оптимален для 2D-рюкзака (упаковка квадратов в двумерный квадрат единичного размера): когда в оптимальной упаковке не более пяти квадратов. ^[35]

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

1. Мэтьюз, Великобритания (25 июня 1897 г.). «О разделении чисел» (PDF) . Труды Лондонского математического общества . 28 : 486–490. дои : 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 г.). «Модель математического программирования для построения тестов и подсчета очков». Наука управления . 19 (8): 961–966. дои : 10.1287/mnsc.19.8.961. JSTOR  2629127.
7. Скиена, СС (сентябрь 1999 г.). «Кто и почему интересуется алгоритмами? Уроки из хранилища алгоритмов Стоуни-Брук». Новости ACM SIGACT . 30 (3): 65–74. CiteSeerX 10.1.1.41.8357 . дои : 10.1145/333623.333627. ISSN  0163-5700. S2CID  15619060. 
8. Пизингер, Д. 2003. Где проблемы с твердым рюкзаком? Технический отчет 2003/08, факультет компьютерных наук, Копенгагенский университет, Копенгаген, Дания.
9. Качетта, Л.; Куланут, А. (2001). «Вычислительные аспекты задач о твердом рюкзаке». Нелинейный анализ . 47 (8): 5547–5558. дои : 10.1016/s0362-546x(01)00658-7.
10. Дж. Джукен, П. Лейман, П. Де Каусмекер, Новый класс примеров сложных задач для задачи о рюкзаке 0–1, Европейский журнал операционных исследований , 301 (3): 841-854, 2022.
11. Пуаррие, Винсент; Янев, Никола; Андонов, Румен (2009). «Гибридный алгоритм решения задачи о неограниченном рюкзаке». Дискретная оптимизация . 6 (1): 110–124. дои : 10.1016/j.disopt.2008.09.004 . ISSN  1572-5286. S2CID  8820628.
12. Дж. Джукен, П. Лейман, П. Де Каусмекер, Особенности задачи о рюкзаке 0-1, основанные на максимальных решениях по включению, Европейский журнал операционных исследований , 311 (1): 36-55, 2023.
13. Войчак, Доминик (2018). «О сильной NP-полноте рациональных задач». Информатика – теория и приложения . Конспекты лекций по информатике. Том. 10846. стр. 308–320. arXiv : 1802.09465 . дои : 10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID  3637366.
14. Добкин, Дэвид; Липтон, Ричард Дж. (1978). «Нижняя граница ½n2 для программ линейного поиска для задачи о рюкзаке». Журнал компьютерных и системных наук . 16 (3): 413–417. дои : 10.1016/0022-0000(78)90026-0.
15. Фактически, нижняя граница применима к задаче о сумме подмножеств, которая является частным случаем Knapsack.
16. Майкл Стил, Дж; Яо, Эндрю С. (1 марта 1982 г.). «Нижние оценки алгебраических деревьев решений». Журнал алгоритмов . 3 (1): 1–8. дои : 10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
17. Бен-Амрам, Амир М.; Галил, Цви (2001), «Топологические нижние границы алгебраических машин произвольного доступа», SIAM Journal on Computing , 31 (3): 722–761, doi : 10.1137/S0097539797329397.
18. auf der Heide, Мейер (1984), «Алгоритм полиномиального линейного поиска для n -мерной задачи о рюкзаке», Journal of the ACM , 31 (3): 668–676, doi : 10.1145/828.322450
19. Андонов, Румен; Пуарье, Винсент; Раджопадхе, Санджай (2000). «Задача о неограниченном рюкзаке: новый взгляд на динамическое программирование». Европейский журнал операционных исследований . 123 (2): 168–181. CiteSeerX 10.1.1.41.2135 . дои : 10.1016/S0377-2217(99)00265-9. 
20. С. Мартелло, П. Тот, Проблемы с рюкзаком: алгоритмы и компьютерные реализации, John Wiley and Sons, 1990
21. С. Мартелло, Д. Пизингер, П. Тот, Динамическое программирование и сильные оценки для задачи о рюкзаке 0-1, Manag. наук. , 45:414–424, 1999.
22. Плато, Г.; Элькихель, М. (1985). «Гибридный алгоритм решения задачи о рюкзаке 0–1». Методы опер. Рез . 49 : 277–293.
23. Мартелло, С.; Тот, П. (1984). «Смесь динамического программирования и метода ветвей и границ для задачи о сумме подмножества». Менеджер. Наука . 30 (6): 765–771. дои : 10.1287/mnsc.30.6.765.
24. Горовиц, Эллис; Сахни, Сартадж (1974), «Вычисление разделов с применением к задаче о рюкзаке», Журнал Ассоциации вычислительной техники , 21 (2): 277–292, doi : 10.1145/321812.321823, hdl : 1813/5989 , MR  0354006, S2CID  16866858
25. Недерлоф, Йеспер; Венгжицкий, Кароль (12 апреля 2021 г.). «Улучшение алгоритма Шреппеля и Шамира для вычисления суммы подмножества с помощью ортогональных векторов». arXiv : 2010.08576 [cs.DS].
26. Шреппель, Ричард; Шамир, Ади (август 1981 г.). «Алгоритм $T = O(2^{n/2})$, $S = O(2^{n/4})$ для некоторых NP-полных задач». SIAM Journal по вычислительной технике . 10 (3): 456–464. дои : 10.1137/0210033. ISSN  0097-5397.
27. Вазирани, Виджай. Алгоритмы аппроксимации. Springer-Verlag Берлин Гейдельберг, 2003 г.
28. Данциг, Джордж Б. (1957). «Экстремальные задачи с дискретной переменной». Исследование операций . 5 (2): 266–288. дои : 10.1287/opre.5.2.266.
29. Кальвин, Джеймс М.; Люнг, Джозеф Ю.-Т. (1 мая 2003 г.). «Анализ жадного алгоритма в среднем для задачи о рюкзаке 0/1». Письма об исследованиях операций . 31 (3): 202–210. дои : 10.1016/S0167-6377(02)00222-5.
30. Лукас, Эндрю (2014). «Формулировки Изинга многих проблем NP». Границы в физике . 2 : 5. arXiv : 1302.5843 . Бибкод : 2014FrP.....2....5L. дои : 10.3389/fphy.2014.00005 . ISSN  2296-424Х.
31. Чанг, TJ и др. Эвристика для оптимизации портфеля с ограничением по мощности. Технический отчет, Лондон SW7 2AZ, Англия: Школа менеджмента, Имперский колледж, май 1998 г.
32. Чанг, CS и др. «Бикритериальная оптимизация тяговых подстанций на основе генетического алгоритма в железнодорожной системе постоянного тока». У Фогеля [102], 11–16.
33. Кулик, А.; Шахнай, Х. (2010). «Для двумерного рюкзака не существует EPTAS» (PDF) . Инф. Процесс. Летт . 110 (16): 707–712. CiteSeerX 10.1.1.161.5838 . дои : 10.1016/j.ipl.2010.05.031. 
34. Коэн, Р. и Гребла, Г. 2014. «Многомерное планирование OFDMA в беспроводной сети с ретрансляционными узлами». в Proc. IEEE INFOCOM'14 , 2427–2435.
35. Ян Лан, Дьёрдь Доса, Синь Хан, Чэньян Чжоу, Аттила Бенко [1]: 2D-рюкзак: Упаковка квадратов , Теоретическая информатика Том. 508, стр. 35–40.
36. Чандра Чекури и Санджив Кханна (2005). «ПТАС для решения задачи о нескольких рюкзаках». SIAM Journal по вычислительной технике . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . дои : 10.1137/s0097539700382820. 
37. Ву, З.Ы.; Ян, YJ; Бай, ФС; Мамедов, М. (2011). «Глобальные условия оптимальности и методы оптимизации квадратичных задач о рюкзаке». J Приложение теории оптимизма . 151 (2): 241–259. дои : 10.1007/s10957-011-9885-4. S2CID  31208118.
38. Галло, Г.; Хаммер, Польша; Симеоне, Б. (1980). «Задачи о квадратном рюкзаке». Комбинаторная оптимизация . Исследования по математическому программированию. Том. 12. С. 132–149. дои : 10.1007/BFb0120892. ISBN 978-3-642-00801-6.
39. Вицгалл, К. (1975). «Математические методы выбора места для систем электронных сообщений (EMS)». Технический отчет NASA Sti/Recon N. Внутренний отчет НБС. 76 : 18321. Бибкод : 1975STIN...7618321W.
40. Ричард М. Карп (1972). «Сводимость среди комбинаторных задач». В Р.Э. Миллере и Дж.В. Тэтчере (редакторы). Сложность компьютерных вычислений. Нью-Йорк: Пленум. стр. 85–103
41. Капрара, Альберто; Келлерер, Ганс; Пферши, Ульрих (2000). «Проблема суммы множественного подмножества». СИАМ Дж. Оптим . 11 (2): 308–319. CiteSeerX 10.1.1.21.9826 . дои : 10.1137/S1052623498348481. 
42. Абед, Фидаа; Чалермсук, Паринья; Корреа, Хосе; Карренбауэр, Андреас; Перес-Лантеро, Пабло; Сото, Хосе А.; Визе, Андреас (2015). О последовательности гильотинной резки. стр. 1–19. doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.1. ISBN 978-3-939897-89-7.

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

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

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

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

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