Задача о ранце - Knapsack problem

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

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

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

Приложения

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

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

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

Определение

Наиболее часто решаемая проблема - это задача о ранце 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. Таким образом, обе версии проблемы имеют одинаковую сложность.

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

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

Решение

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

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

Задача о неограниченном рюкзаке ( 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} + м [ш-ш_ {н}])}$${\ displaystyle w_ {i} \ leq w}$${\ displaystyle v_ {i}}$${\ displaystyle i}$

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

Здесь максимум пустого множества принимается равным нулю. Табулирование результатов сверху вниз дает решение. Поскольку вычисление каждого из них включает в себя проверку не более чем элементов, а для расчета доступно не более значений , время работы решения динамического программирования составляет . Разделение на их наибольший общий делитель - способ сократить время работы. ${\ displaystyle m [0]}$${\ displaystyle m [Вт]}$${\ Displaystyle м [ш]}$${\ displaystyle n}$${\ displaystyle W}$${\ Displaystyle м [ш]}$${\ 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 м [я, ш]}$${\ displaystyle w}$${\ displaystyle i}$${\ displaystyle i}$

Мы можем определить рекурсивно следующим образом: (Определение A)${\ Displaystyle м [я, ш]}$

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

Затем решение можно найти путем расчета . Чтобы сделать это эффективно, мы можем использовать таблицу для хранения предыдущих вычислений. ${\ displaystyle 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 0 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])

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

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

// 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
        value[i-1, j] = 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
            value[i-1, j-w[i]] = 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. Итак,

${\ displaystyle {\ begin {align} & 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 \ \\ конец {выровнен}}}$

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

${\ displaystyle {\ begin {align} & 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 \\\ конец {выровнен}}}$

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

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

/**
 * 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. когда большая по сравнению с п . В частности, если неотрицательные, но не целые числа, мы все равно можем использовать алгоритм динамического программирования путем масштабирования и округления (то есть с использованием арифметики с фиксированной точкой ), но если проблема требует дробных цифр точности для получения правильного ответа, потребуется масштабирование , а алгоритм DP потребует пространства и времени. ${\ displaystyle W}$${\ displaystyle w_ {i}}$${\ displaystyle d}$${\ displaystyle W}$${\ displaystyle 10 ^ {d}}$${\ displaystyle O (W10 ^ {d})}$${\ displaystyle 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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема: Множество, вычисленное описанным выше алгоритмом, удовлетворяет , где - оптимальное решение. ${\ displaystyle S '}$${\ Displaystyle \ mathrm {прибыль} (S ') \ geq (1- \ varepsilon) \ cdot \ mathrm {прибыль} (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}$

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

${\ 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 х \ в Z _ {+} ^ {п}}$

где и . Вектор обозначает количество копий каждого члена . ${\ Displaystyle \ альфа \ в 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 х \ в Z _ {+} ^ {п}}$${\ Displaystyle \ альфа = 1}$${\ displaystyle V = v_ {i}}$${\ displaystyle W = w_ {i}}$${\ displaystyle J}$

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

-Й элемент порог доминировал на , записываются как , если некоторое количество копий преобладают . Формально, а для некоторых и . Это обобщение коллективного доминирования, впервые введенное и использованное в алгоритме EDUK. Наименьшее из таких определяет порог написания пункта . В этом случае оптимальное решение может содержать не больше копий .${\ displaystyle i}$${\ displaystyle J}$${\ Displaystyle я \ пре \ пре 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 х \ в Z _ {+} ^ {п}}$${\ displaystyle \ alpha \ geq 1}$${\ displaystyle \ alpha}$${\ displaystyle i}$${\ Displaystyle т_ {я} = (\ альфа -1) ш_ {я}}$${\ 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 я \ ll _ {\ эквив} 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}$

Вариации

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

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

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

В качестве примера предположим, что вы управляете круизным лайнером. Вы должны решить, сколько известных комиков нанять. Эта лодка может вместить не более одной тонны пассажиров, а вес артистов должен быть менее 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. Однако показано, что алгоритм эффективно решает разреженные экземпляры. Экземпляр многомерного рюкзака разрежен , если существует множество для таких , что для каждого рюкзаке элемента , таким образом, что и . Такие случаи возникают, например, при планировании пакетов в беспроводной сети с узлами ретрансляции. Алгоритм from также решает редкие экземпляры варианта с множественным выбором, многомерного рюкзака с множественным выбором. ${\ displaystyle D = 2}$${\ displaystyle =}$${\ Displaystyle J = \ {1,2, \ ldots, м \}}$${\ displaystyle m <D}$${\ displaystyle i}$${\ Displaystyle \ существует г> м}$${\ displaystyle \ forall j \ in J \ cup \ {z \}, \ w_ {ij} \ geq 0}$${\ displaystyle \ forall y \ notin J \ cup \ {z \}, w_ {iy} = 0}$

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

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

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

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

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

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

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

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

Задача о геометрическом рюкзаке

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

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

Примечания

использованная литература

• Гарей, Майкл Р .; Дэвид С. Джонсон (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 (программное обеспечение для оптимизации)