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

редактировать

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

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

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

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

Содержание

1 Приложения
2 Определение
3 Вычислительная сложность
4 Решение
- 4.1 Алгоритм предварительного динамического программирования
  - 4.1.1 Задача с рюкзаком 0-1
- 4.2 Встреча посередине
- 4.3 Алгоритмы аппроксимации
  - 4.3.1 Алгоритм жадной аппроксимации
  - 4.3.2 Полностью полиномиальная схема аппроксимации по времени
- 4.4 Отношения доминирования
5 Вариации
- 5.1 Мульти- объективная задача о ранце
- 5.2 Многомерная задача о рюкзаке
- 5.3 Многократная задача о ранце
- 5.4 Квадратичная задача о ранце
- 5.5 Задача о сумме подмножеств
6 См. также
7 Примечания
8 Ссылки
9 Внешние ссылки

Приложения

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

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

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

Определение

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

увеличить

∑ i = 1 nvixi {\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

\sum _{i=1}^{n}v_{i}x_{i}

при условии

∑ i = 1 nwixi ≤ W {\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

xi ∈ {0, 1} {\ displaystyle x_ { i} \ in \ {0,1 \}}

x_{i}\in \{0,1\}

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

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

maximize

∑ i = 1 nvixi {\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

\sum _{i=1}^{n}v_{i}x_{i}

при условии

∑ i = 1 nwixi ≤ W {\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

xi ∈ {0, 1, 2,…, c}. {\ displaystyle x_ {i} \ in \ {0,1,2, \ dots, c \}.}

x_{i}\in \{0,1,2,\dots,c\}.

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

увеличить

∑ i = 1 nvixi {\ displaystyle \ sum _ {i = 1} ^ {n} v_ {i} x_ {i}}

\sum _{i=1}^{n}v_{i}x_{i}

при условии

∑ i = 1 nwixi ≤ W {\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W}

\sum _{i=1}^{n}w_{i}x_{i}\leq W

xi ≥ 0, xi ∈ Z. {\ displaystyle x_ {i} \ geq 0, \ x_ {i} \ in \ mathbb {Z}.}

x_{i}\geq 0,\ x_{i}\in \mathbb {Z}.

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

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

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

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

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

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

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

Решение

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

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

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

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

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

при условии

∑ i = 1 nwixi ≤ w ′ {\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq w '}

\sum _{i=1}^{n}w_{i}x_{i}\leq w'

xi>0 {\ displaystyle x_ {i}>0}

x_i>0

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

1. $m [0] = 0 {\ displaystyle m [0] = 0 \, \!}$ $m[0]=0\,\!$ (сумма нулевых элементов, т. Е. Сумма пустого набора).

2. $m [w] = max (v 1 + m [w - w 1], v 2 + m [w - w 2],..., vi + m [w - wi]) {\ displaystyle m [ w] = \ max (v_ {1} + m [w-w_ {1}], v_ {2} + m [w-w_ {2}],..., v_ {i} + m [w-w_ {i}])}$ $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{i}+m[w-w_{i}])$ , $wi ≤ w {\ displaystyle w_ {i} \ leq w}$ $w_{i}\leq w$ , где $vi {\ displaystyle v_ {i}}$ $v_{i}$ - значение элемента $i {\ displaystyle i}$ $i$ -го типа.

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

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

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

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

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

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

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

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

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

1 // Ввод: 2 // Значения (хранятся в массиве v) 3 // Вес s (хранится в массиве w) 4 // Количество отдельных элементов (n) 5 // Вместимость рюкзака (Вт) 6 // ПРИМЕЧАНИЕ: предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1. 7 8 для j от 0 до W do: 9 m [0, j]: = 0 10 11 для i от 1 до n do: 12 для j от 0 до W do: 13 если w [i]>j, то : 14 m [i, j]: = m [i-1, j] 15 else: 16 m [i, j]: = max (m [i-1, j], m [i-1, jw [i ]] + v [i])

Следовательно, это решение будет выполняться за $O (n W) {\ displaystyle O (nW)}$ $O(nW)$ времени и $O (n W) {\ displaystyle O (nW)}$ $O(nW)$ пробел.

Однако, если мы сделаем еще один или два шага, мы должны знать, что метод будет работать в промежутке времени между $O (n W) {\ displaystyle O (nW)}$ $O(nW)$ и $О (2 n) {\ displaystyle O (2 ^ {n})}$ $O(2^{n})$ . Из определения A мы можем узнать, что нет необходимости в вычислении всех весов, когда количество элементов и сами элементы, которые мы выбрали, фиксированы. Иными словами, приведенная выше программа вычисляет больше, чем ожидалось, потому что вес все время меняется от 0 до W. Все, что нам нужно сделать, это сравнить m [i-1, j] и m [i-1, jw [i]] + v [i] для m [i, j], и когда m [i-1, jw [i]] вне допустимого диапазона, мы просто даем значение m [i-1, j] для m [i, j]. С этой точки зрения мы можем запрограммировать этот метод так, чтобы он выполнялся рекурсивно.

1 // Ввод: 2 // Значения (хранятся в массиве v) 3 // Вес (хранятся в массиве w) 4 // Количество отдельных элементов (n) 5 // Вместимость рюкзака (Вт) 6 // ПРИМЕЧАНИЕ : Предполагается, что массив «v» и массив «w» хранят все соответствующие значения, начиная с индекса 1. 7 8 Определить значение [n, W] 9 10 Инициализировать все значение [i, j] = -1 11 12 Определить m: = (i, j) // Определим функцию m так, чтобы она представляла максимальное значение, которое мы можем получить при условии: используйте первые i элементов, общий предел веса равен j 13 {14, если i == 0 или j <= 0 then: 15 value[i, j] = 0 16 return 17 18 if (value[i-1, j] == -1) then: // m[i-1, j] has not been calculated, we have to call function m 19 value[i-1, j] = m(i-1, j) 20 21 if w[i]>j, тогда : // элемент не помещается в сумке (ЭТО НЕ УДАЛОСЬ В ПРЕДЫДУЩЕМ АЛГОРИТМЕ) 22 value [i, j] = value [i-1, j] 23 else: 24 if (value [i-1, jw [i] ] == -1), то: // m [i-1, jw [i]] не было вычислено, мы должны вызвать функцию m 25 value [i-1, jw [i]] = m (i-1, jw [i]) 26 значение [i, j] = max (значение [i-1, j], значение [i-1, jw [i]] + v [i]) 27} 28 29 Запуск m (n, W)

Например, существует 10 различных элементов, а ограничение по весу составляет 67. Итак,

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 {\ 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 \\\ end {align}}}

{\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) {\ displaystyle m (10,67)}$ $m(10,67)$ , вы получите (исключая вызовы, которые производят m (i, j) = 0):

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, м (7, 37) = 505 m (6, 67) = 1183, m (6, 41) = 725, m (6, 40) = 678, m (6, 38) = 678, m (6, 37) = 505 м (5, 67) = 1183, м (5, 41) = 725, м (5, 40) = 678, м (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 {\ 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, м (6,40) = 678, м (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 {align}}}

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

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

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

Другой алгоритм для рюкзака 0-1, обнаруженный в 1974 году и иногда называемый «встречей посередине» из-за параллелей с a Алгоритм с аналогичным названием в{i}} <30><31>J = \ {1,2, \ ldots, m \} <31><32>{\ displaystyle m [w <32><33>w_ {i}>w \, \! <33><34>\ alpha = 1 <34><35>(W_ {1}, \ ldots, W_ {D}) <35><36>{\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ geq v_ {i}} <36><37>{\ displaystyle S_ {1} \ cup S_ {2} } <37><38>m <39>{\ displaystyle {\ begin {выровнено} 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, м (1,38) = 505, м (1,37) = 505, м (1,35) = 505, м (1,29) = 505, м (1,23) = 505 \ конец {выровнено}}} <39><40>D = 2 <40><41>x <41><42>{\ displaystyle O (n2 ^ {n / 2})} <42><43>{\ overline {w_ {i}}} = (w_ {i1}, \ ldots, w_ {iD}) <43><44>\ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W <44><45>{\ displaystyle w_ {j} \, x_ {j} \ \ leq w_ {i}} <45><46>{\ displaystyle S_ {2} = \ left \ {k + 1 \ right \}} <46><47>\ exists z>m <47><48>\ sum _ {i = 1} ^ {n} v_ {i} x_ {i} <48><49>\ alpha <49><50>J = \ {j \}, \ alpha = 1, x_ {j} = \ lfloor {\ frac {w_ {i}} {w_ {j}}} \ rfloor <50><51>{ \ displaystyle x_ {i} \ in \ {0,1,2, \ dots, c \}.} <51><52>b <52><53>{\ displaystyle v_ {j} \, x_ {j} \ \ geq v_ {i}} <53><54>i \ ll _ {m} j <54><55>i \ Prec \ Prec J <55><56>10 ^ {d} <56><57>v <57><58>O (2 ^ {n}) <58><59>\ forall y \ notin J \ cup \ {z \}, w_ {iy} = 0 <59><60>t_ { я} = (\ альфа -1) w_ {i} <60><61>значок <61><62>{\ displaystyle m [w] = \ max (v_ {1} + m [w-w_ {1} ], v_ {2} + m [w-w_ {2}],..., v_ {i} + m [w-w_ {i}])} <62><63>m [0, \, w ] = 0 <63><64>{\ displaystyle \ left \ lfloor {\ frac {v_ {i}} {K}} \ right \ rfloor} <64><65>{\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ \ leq w_ {i}} <65><66>S_ {1} <66><67>S_ {2} <67><68>{\ 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 \\\ end { выровнено}}} <68><69>{\ displaystyle {\ frac {P} {n}}} <69><70>O (nW) <70><71>{\ displaystyle k = \ textstyle \ max _ {1 \ leq k <71><72>{\ displaystyle w-w_ {1}, w-w_ {2},..., w-w_ {i}} <72><73>i \ n ot \ in J <73><74>O (n2 ^ {n}) <74><75>j <75><76>d <76><77>i <77><78>\ forall j \ in J \ cup \ {z \}, \ w_ {ij} \ geq 0 <78><79>m <79><80>J = \ {b, j \}, \ alpha = 1, x_ {b} = t, x_ {j} = 1 <80><81>{\ frac {v_ {b}} {w_ {b}}} \ geq {\ frac {v_ {i}} {w_ {i}}} \, <81><82>{\ displaystyle \ sum _ {j \ in J} v_ {j} \, x_ {j} \ \ geq \ alpha \, v_ {i} \,} <82><83>S ^ {*} <83><84>m [n, W] <84><85>n <85><86>{\ displaystyle S_ {1} = \ left \ {1, \ ldots, k \ right \} } <86><87>m [i, w] <87><88>\ {v_ {i} \ mid 1 \ leq i \ leq n \} <88><89>w_ {i} \ leqslant w <89><90>w_ {1}, \, w_ {2}, \, \ ldots, \, w_ {n}, \, W <90><91>i \ ll J <91><92>x_i>0 <92><93>c <93><94>{\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq w <94><95>m [0] = 0 \, \! <95><96>{\ displaystyle O (nW10 ^ {d})} <96><97>м [Вт] <97><98>м / 2 <98><99>{ \ displaystyle x_ {i} \ geq 0, \ x_ {i} \ in \ mathbb {Z}.} <99><100>\ qquad \ sum _ {j \ in J} w_ {j} \, x_ {j } \ \ leq \ alpha \, w_ {i} <100><101>x_ {i} \ in \ {0,1 \} <101><102>v_ {j} + tv_ {b} \ geq v_ { i} <102><103>{\ displaystyle \ sum _ {j \ in J} w_ {j} \, x_ {j} \ leq \ alpha \, w_ {i}} <103><104>J <104><105>w <105><106>m [i, \, w] = m [i-1, \, w] <106>html