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

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

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

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

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

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

Приложения

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

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

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

Определение

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

максимизировать $\sum _{i=1}^{n}v_{i}x_{i}$

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

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

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

максимизировать $\sum _{i=1}^{n}v_{i}x_{i}$

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

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

максимизировать $\sum _{i=1}^{n}v_{i}x_{i}$

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

при условии $\sum _{i=1}^{n}w_{i}x_{i}\leq w'$ и $x_{i}>0$

Обратите внимание, что $m[w]$ имеет следующие свойства:

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

2. $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ , $w_{i}\leq w$, где $v_{i}$ это ценность $i$-ый вид предмета.

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

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

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

0-1 проблема с рюкзаком

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

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

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

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

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

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

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 1 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

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

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

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

Define value[n, W]

Initialize all value[i, j] = -1

Define m:=(i,j)         // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
{
    if i == 0 or j <= 0 then:
        value[i, j] = 0
        return

    if (value[i-1, j] == -1) then:     // m[i-1, j] has not been calculated, we have to call function m
        m(i-1, j)

    if w[i] > j then:                      // item cannot fit in the bag
        value[i, j] = value[i-1, j]
    else: 
        if (value[i-1, j-w[i]] == -1) then:     // m[i-1,j-w[i]] has not been calculated, we have to call function m
            m(i-1, j-w[i])
        value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
}

Run m(n, W)

Например, существует 10 разных предметов, а предел веса — 67. Итак, $${\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}}$$ Если вы используете вышеуказанный метод для вычисления $m(10,67)$, вы получите это, исключая вызовы, которые производят $m(i,j)=0$: $${\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}}$$

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

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

/**
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
 */
function knapsack(i: int, j: int): Set<int> {
    if i == 0 then:
        return {}
    if m[i, j] > m[i-1, j] then:
        return {i} ∪ knapsack(i-1, j-w[i])
    else:
        return knapsack(i-1, j)
}

knapsack(n, W)

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

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

algorithm Meet-in-the-middle is
    input: A set of items with weights and values.
    output: The greatest combined value of a subset.

    partition the set {1...n} into two sets A and B of approximately equal size
    compute the weights and values of all subsets of each set

    for each subset of A do
        find the subset of B of greatest value such that the combined weight is less than W

    keep track of the greatest combined value seen so far

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

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

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

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

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

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

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

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

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

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

algorithm FPTAS is 
    input: ε ∈ (0,1]
           a list A of n items, specified by their values, $v_{i}$, and weights
    output: S' the FPTAS solution

    P := max $\{v_{i}\mid 1\leq i\leq n\}$  // the highest item value
    K := ε ${\frac {P}{n}}$

    for i from 1 to n do
        $v'_{i}$ := $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$
    end for

    return the solution, S', using the $v'_{i}$ values in the dynamic program outlined above

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

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

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

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

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

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

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

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

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

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

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

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

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

The $i$-th элемент многократно доминирует один элемент $j$, записанный как $i\ll _{m}j$, если $i$ преобладает некоторое количество копий $j$. Формально, $w_{j}\,x_{j}\ \leq w_{i}$, и $v_{j}\,x_{j}\ \geq v_{i}$ для некоторых $x_{j}\in Z_{+}$ то есть $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$. Это доминирование можно эффективно использовать во время предварительной обработки, поскольку его можно относительно легко обнаружить.

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

Позволять $b$ быть лучшим предметом , т.е. ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ для всех $i$. Это предмет с наибольшей плотностью стоимости. $i$-th элемент модульно доминирует один элемент $j$, записанный как $i\ll _{\equiv }j$, если $i$ преобладает $j$ плюс несколько копий $b$. Формально, $w_{j}+tw_{b}\leq w_{i}$, и $v_{j}+tv_{b}\geq v_{i}$ то есть $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$.

Вариации

Основная статья: Список проблем с рюкзаком

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Гэри, Майкл Р .; Дэвид С. Джонсон (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  978-0-7167-1045-5 . А6: MP9, стр. 247.
• Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком . Спрингер. дои : 10.1007/978-3-540-24777-7 . ISBN  978-3-540-40286-2 . МР   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 (программное обеспечение для оптимизации)