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

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

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

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

Приложения [ править ]

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

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

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

Определение [ править ]

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

максимизировать ${\ Displaystyle \ сумма _ {я = 1} ^ {п} v_ {я} x_ {я}}$

при условии и .${\ displaystyle \ sum _ {я = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ Displaystyle х_ {я} \ в \ {0,1 \}}$

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

Задача с ограниченным рюкзаком ( BKP ) снимает ограничение, согласно которому существует только один предмет каждого вида , но ограничивает количество копий каждого вида предмета до максимального неотрицательного целого числа :${\ displaystyle x_ {i}}$${\ displaystyle c}$

максимизировать ${\ Displaystyle \ сумма _ {я = 1} ^ {п} v_ {я} x_ {я}}$

при условии и${\ displaystyle \ sum _ {я = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ displaystyle x_ {i} \ in \ {0,1,2, \ dots, c \}.}$

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

максимизировать ${\ Displaystyle \ сумма _ {я = 1} ^ {п} v_ {я} x_ {я}}$

при условии и${\ displaystyle \ sum _ {я = 1} ^ {n} w_ {i} x_ {i} \ leq W}$${\ displaystyle x_ {i} \ geq 0, \ x_ {i} \ in \ mathbb {Z}.}$

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

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

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

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

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

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

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

Решение [ править ]

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

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

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

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

при условии и${\ Displaystyle \ сумма _ {я = 1} ^ {п} ш_ {я} х_ {я} \ leq ш '}$${\ displaystyle x_ {i}> 0}$

Обратите внимание, что он имеет следующие свойства:${\ Displaystyle м [ш]}$

1. (сумма нулевых элементов, т.е. суммирование пустого множества).${\ Displaystyle м [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]}$ O ( n 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.для  j  от  0  до  W  делаем : m [ 0 ,  j ]  : =  0для  i  от  1  до  n  делаем : для  j  от  0  до  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 ])

Следовательно, это решение будет работать во времени и пространстве.${\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 возвращаться if  ( value [ i -1 ,  j ]  ==  -1 )  then :  // m [i-1, j] не было вычислено, мы должны вызвать функцию m значение [ i -1 ,  j ]  =  m ( i -1 ,  j ) if  w [ i ]  >  j  then :  // товар не помещается в сумке значение [ i ,  j ]  =  значение [ i -1 ,  j ] еще :  if  ( value [ i -1 ,  j - w [ i ]]  ==  -1 )  then :  // m [i-1, jw [i]] не было вычислено, мы должны вызвать функцию m значение [ i -1 ,  j - w [ i ]]  =  m ( i -1 ,  j - w [ i ]) значение [ i ,  j ]  =  max ( значение [ 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 ) :  Set < int >  { если  i  ==  0,  то : возврат  {} если  m [ i ,  j ]  >  m [ i -1 ,  j ],  то : return  { i }  ∪  рюкзак ( i -1 ,  j - w [ i ]) еще : возвратный  рюкзак ( i -1 ,  j )}рюкзак ( n ,  W )

Встреча посередине [ править ]

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

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

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

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

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

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

Алгоритм 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  : = конец для${\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^{*}}$

Отношения доминирования [ править ]

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

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

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

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

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

Варианты [ править ]

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

Задача о многоцелевом рюкзаке [ править ]

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

В качестве примера предположим, что вы управляете круизным лайнером. Вы должны решить, сколько известных комиков нанять. Эта лодка может вместить не более одной тонны пассажиров, а вес артистов должен быть менее 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. ^[23] Однако показано , что алгоритм из ^[24] эффективно решает разреженные экземпляры. Экземпляр многомерного рюкзака разрежен , если существует множество для таких , что для каждого рюкзаке элемента , таким образом, что и . Такие случаи возникают, например, при планировании пакетов в беспроводной сети с узлами ретрансляции. ^[24] Алгоритм из ^[24] также решает редкие экземпляры варианта с множественным выбором, многомерного рюкзака с множественным выбором.${\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 (полка увеличения высоты) оптимален для двухмерного ранца (упаковка квадратов в двумерный квадрат единичного размера): когда в оптимальной упаковке находится не более пяти квадратов. ^[25]

Задача с несколькими рюкзаками [ править ]

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

Квадратичная задача о рюкзаке [ править ]

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

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

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

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

Задача о геометрическом рюкзаке [ править ]

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

См. Также [ править ]

Заметки [ править ]

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

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

Внешние ссылки [ править ]

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

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