Викиконспекты - Вклад участника [ru]

Сортировка пузырьком

2014-06-16T21:34:16Z

94.26.129.35: /* Источники информации */

'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.

== Алгоритм ==
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.

== Псевдокод ==
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> a[0..n - 1] </tex>.
'''function''' bubbleSort(a):
'''for''' i = 0 '''to''' n - 2
'''for''' j = 0 '''to''' n - 2
'''if''' a[j] > a[j + 1]
swap(a[j], a[j + 1])

== Оптимизация ==
* Можно заметить, что после <tex> i </tex>-ой итерации внешнего цикла <tex> i </tex> последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до <tex> n - 2 </tex>, а до <tex> n - i - 2 </tex>.
* Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не <tex> n - 1 </tex> раз, а до тех пор, пока во внутреннем цикле происходят обмены.

При использовании первой оптимизации сортировка принимает следующий вид:
'''function''' bubbleSort(a):
'''for''' i = 0 '''to''' n - 2
'''for''' j = 0 '''to''' n - i - 2
'''if''' a[j] > a[j + 1]
swap(a[j], a[j + 1])

При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
'''function''' bubbleSort(a):
i = 0
t = ''true''
'''while''' t
t = ''false''
'''for''' j = 0 '''to''' n - i - 2
'''if''' a[j] > a[j + 1]
swap(a[j], a[j + 1])
t = ''true''
i = i + 1

== Сложность ==
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим все необходимые обмены элементов.

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <tex> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>.

В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <tex> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>.

В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>.

== Пример работы алгоритма ==

Возьмём массив <tex> [5, 1, 4, 2, 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

'''Первый проход:'''

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| После
!style="background-color:#EEE"| Описание шага
|-
|style="background-color:#FFF;padding:2px 10px"| '''5 1''' 4 2 8
|style="background-color:#FFF;padding:2px 10px"| '''1 5''' 4 2 8
|style="background-color:#FFF;padding:2px 10px"| Здесь алгоритм сравнивает два первых элемента и меняет их местами.
|-
|style="background-color:#FFF;padding:2px 10px"| 1 '''5 4''' 2 8
|style="background-color:#FFF;padding:2px 10px"| 1 '''4 5''' 2 8
|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 5 > 4
|-
|style="background-color:#FFF;padding:2px 10px"| 1 4 '''5 2''' 8
|style="background-color:#FFF;padding:2px 10px"| 1 4 '''2 5''' 8
|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 5 > 2
|-
|style="background-color:#FFF;padding:2px 10px"| 1 4 2 '''5 8'''
|style="background-color:#FFF;padding:2px 10px"| 1 4 2 '''5 8'''
|style="background-color:#FFF;padding:2px 10px"| Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.
|}

'''Второй проход:'''

{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE"| До
!style="background-color:#EEE"| После
!style="background-color:#EEE"| Описание шага
|-
|style="background-color:#FFF;padding:2px 10px"| '''1 4''' 2 5 8
|style="background-color:#FFF;padding:2px 10px"| '''1 4''' 2 5 8
|style="background-color:#FFF;padding:2px 10px"|
|-
|style="background-color:#FFF;padding:2px 10px"| 1 '''4 2''' 5 8
|style="background-color:#FFF;padding:2px 10px"| 1 '''2 4''' 5 8
|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 4 > 2
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''4 5''' 8
|style="background-color:#FFF;padding:2px 10px"| 1 2 '''4 5''' 8
|style="background-color:#FFF;padding:2px 10px"|
|-
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 '''5 8'''
|style="background-color:#FFF;padding:2px 10px"| 1 2 4 '''5 8'''
|style="background-color:#FFF;padding:2px 10px"|
|}

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

== Модификации ==

=== Сортировка чет-нечет ===
'''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.
Псевдокод указан ниже:
'''function''' oddEvenSort(a):
'''for''' i = 0 '''to''' n - 1
'''if''' i '''mod''' 2 = 0
'''for''' j = 2 '''to''' n - 1 '''step''' 2
'''if''' a[j] < a[j - 1]
swap(a[j - 1], a[j])
'''else'''
'''for''' j = 1 '''to''' n - 1 '''step''' 2
'''if''' a[j] < a[j - 1]
swap(a[j - 1], a[j])

Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.

=== Сортировка расческой ===
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:

'''function''' combSort(a):
k = 1.3
jump = n
'''bool''' swapped = ''true''
'''while''' jump > 1 '''and''' swapped
'''if''' jump > 1
jump /= k
swapped = ''false''
'''for''' i = 0 '''to''' size - jump - 1
'''if''' a[i + jump] < a[i]
swap(a[i], a[i + jump])
swapped = ''true''
Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex> n/k </tex>, где <tex> k =1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

=== Сортировка перемешиванием ===
'''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

'''function''' shakerSort(a):
begin = -1
end = n - 2
'''while''' swapped
swapped = ''false''
begin++
'''for''' i = begin '''to''' end
'''if''' a[i] > a[i + 1]
swap(a[i], a[i + 1])
swapped = ''true''
'''if''' swapped = false
'''break'''
swapped = ''false''
end--
'''for''' i = end '''downto''' begin
'''if''' a[i] > a[i + 1]
swap(a[i], a[i + 1])
swapped = ''true''

== См. также ==
* [[Сортировка выбором]]
* [[Сортировка вставками]]
* [[Сортировка кучей]]
* [[Сортировка слиянием]]
* [[Быстрая сортировка]]
* [[Сортировка подсчетом]]

== Источники информации ==
* [http://en.wikipedia.org/wiki/Bubble_sort Сортировка пузырьком {{---}} Википедия]
* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор]
* [http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет {{---}} Википедия]
* [http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой {{---}} Википедия]
* [http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием {{---}} Википедия]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Сортировка]]

Преобразование Барроуза-Уилера

2014-01-06T12:35:59Z

94.26.129.35: /* Описание алгоритма */

== Определение ==

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

== Описание алгоритма ==

Преобразование выполняется в три этапа.
* Cоставляется таблица всех циклических сдвигов входной строки.
* Производится лексикографическая (в алфавитном порядке) сортировка строк таблицы.
* В качестве выходной строки выбрается последний столбец таблицы преобразования и номер строки, совпадающей с исходной.

== Пример работы алгоритма ==

Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA"''.

{| border="1"
!colspan="4"|Трансформация
|-
! Вход || Все Перестановки || Сортировка Строк || Выход
|-
|
ABACABA
|
ABACABA
BACABAA
ACABAAB
CABAABA
ABAABAC
BAABACA
AABACAB
|
AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA
|
BCABAAA
|}

Результат можно записать так: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3), где 3 {{---}} это номер исходной строки в отсортированной матрице, так как он нужен для обратного преобразования.

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

Пусть нам дана исходная строка <tex>s = </tex>''"ABACABA$"''.

{| border="1"
!colspan="4"|Трансформация
|-
! Вход || Все Перестановки || Сортировка Строк || Выход
|-
|
ABACABA$
|
ABACABA$
BACABA$A
ACABA$AB
CABA$ABA
ABA$ABAC
BA$ABACA
A$ABACAB
$ABACABA

|
ABACABA$
ABA$ABAC
ACABA$AB
A$ABACAB
BACABA$A
BA$ABACA
CABA$ABA
$ABACABA
|
$CBBAAAA
|}

При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной: (''"ABACABA$"''). Тогда результат можно записать так: <tex>BWT(s)=</tex>''"$CBBAAAA"''.

== Обратное преобразование ==

===Наивный алгоритм===

Пусть нам дано: <tex>BWT(s)=</tex>(''"BCABAAA"'', 3). Тогда выпишем в столбик нашу преобразованную последовательность символов ''"BCABAAA"''. Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза {{---}} Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем ''"BCABAAA"''. Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку.
Алгоритм обратного преобразования описан в таблице ниже:

{| border="1"
!colspan="8"| Обратное преобразование
|-
!colspan="8"| Вход
|-
|align="center" colspan="8"|
BCABAAA
|-
! Добавление 1 || Сортировка 1 || Добавление 2 || Сортировка 2 || Добавление 3 || Сортировка 3 || Добавление 4
|-align="right"
|
B
C
A
B
A
A
A
|
A
A
A
A
B
B
C
|
BA
CA
AA
BA
AB
AB
AC
|
AA
AB
AB
AC
BA
BA
CA
|
BAA
CAB
AAB
BAC
ABA
ABA
ACA
|
AAB
ABA
ABA
ACA
BAA
BAC
CAB
|
BAAB
CABA
AABA
BACA
ABAA
ABAC
ACAB
|-
! Сортировка 4 || Добавление 5 || Сортировка 5 || Добавление 6 || Сортировка 6 || Добавление 7 || Сортировка 7

|-align="right"
|
AABA
ABAA
ABAC
ACAB
BAAB
BACA
CABA
|
BAABA
CABAA
AABAC
BACAB
ABAAB
ABACA
ACABA
|
AABAC
ABAAB
ABACA
ACABA
BAABA
BACAB
CABAA
|
BAABAC
CABAAB
AABACA
BACABA
ABAABA
ABACAB
ACABAA
|
AABACA
ABAABA
ABACAB
ACABAA
BAABAC
BACABA
CABAAB
|
BAABACA
CABAABA
AABACAB
BACABAA
ABAABAC
ABACABA
ACABAAB
|
AABACAB
ABAABAC
ABACABA
ACABAAB
BAABACA
BACABAA
CABAABA
|-

!colspan="8"| Результат
|-
|align="center" colspan="8"|
ABACABA
|}

Следует также заметить, что если нам было бы дано <tex>BWT(s)=</tex>''"$CBBAAAA"'', то мы также получили бы нашу исходную строку, только с символом конца строки ''$'' на конце: ''ABACABA$''.

Как несложно посчитать сложность данного алгоритма <tex>O(N^3logN) </tex>, также он требует <tex>O(N^2)</tex> памяти.

===Оптимизация===

Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении неизвестного столбца выполнялись одни и те же действия. Мы приписывали новый столбец и сортировали имеющиеся данные. На каждом шагу мы к строке, которая находилась на <tex> i </tex>-ом месте приписываем в начало <tex> i </tex> -ый элемент столбца входных данных. Пусть изначально мы знаем каким по порядку является приписанный нами в начало символ (то есть каким по порядку в столбце). И конечно же мы знаем исходя из предыдущего шага какое место занимала наша строка без этого первого символа (<tex> i </tex> -ое). Тогда несложно заметить, что при выполнении такой операции строка с номером <tex> i </tex> всегда будет перемещаться на позицию с номером <tex> j </tex>.

{| border="1"
|0||а||     ||р||9
|-
|1||а||||д||7
|-
|2||а|| ||a||0
|-
|3||а|| ||к||8
|-
|4||а|| ||р||10
|-
|5||б|| ||a||1
|-
|6||б|| ||a||2
|-
|7||д|| ||a||3
|-
|8||к|| ||a||4
|-
|9||р|| ||б||5
|-
|10||р|| ||б||6
|}

Здесь слева это отсортированный данный столбец, чтобы мы знали какое место в лексикографическом порядке занимает приписываемый нами символ среди всех элементов данного нам изначально столбца. Справа - изначально данный столбец и соответствующее ему число. Поскольку мы в нашем алгоритме новый столбец приписываем в начало, то мы из состояния <tex> i </tex> (левый столбец) переходим в состояние <tex> j </tex> (правый). Для того, чтобы восстановить строку, нам необходимо от последней такой цифры по пути из <tex> j </tex> в <tex> i </tex> восстановить строку.
{|
|
{| border="1"
|6
|→
|10
|→
|4
|→
|8
|→
|3
|→
|7
|→
|1
|→
|5
|→
|9
|→
|0
|→
|2
|-
|а
|
|б
|
|р
|
|а
|
|к
|
|а
|
|д
|
|а
|
|б
|
|р
|
|а
|}
===Сложность оптимизированного алгоритма===
Данный алгоритм работает за <tex>O(NlogN)</tex> действий и требует <tex>O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения первого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>O(N+M)</tex> действий и требует <tex>O(N+M)</tex> памяти, где <tex>M</tex> — размер алфавита.

===Псевдокод оптимизированного алгоритма===
Пусть <tex> N </tex> — количество символов во входной строке, <tex> M </tex> — количество символов в алфавите, <tex> k </tex> — номер исходной строки в матрице перестановок, <tex> s </tex> — входящая строка, <tex> count </tex> — массив для сортировки подсчетом, <tex> t </tex> — вектор обратного преобразования, <tex> x </tex> — номер данной нам строки в таблице.

// Cчитаем частоты символов
for i = 0 .. M
count[i] = 0
for i = 0 .. N
count[s[i]]++
// Упорядочиваем символы, чтобы получить первый столбец исходной матрицы
// count[i] указывает на первую позицию символа i в первом столбце
sum = 0
for i = 0 .. M
sum = sum + count[i]
count[i] = sum - count[i]
// Cоздаем вектор обратного преобразования
for i = 0 .. N
t[count[s[i]]] = i
count[s[i]]++
// И восстанавливаем исходный текст
j = t[x]
for i = 0 .. N
print(s[j])
j = t[j]

===Доказательство корректности===

Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево:
:{|
<tex> S_{k}T = T[(j + k) (mod\ N + 1)] </tex>
|}

Существует перестановка <tex>p</tex> чисел <tex>\{0, ..., N\}</tex>, которая удовлетворяет условию:
:{|
<tex> S_{p(i)}T \preceq S_{p(i + 1)}T,\ i = 0, ..., N - 1\ \ \textbf{(1)}</tex>
|}

Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением:
:{|
<tex>B[i] = S_{p(i)}T[N]</tex>, другими словами <tex>B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (mod\ N + 1)] \ \ \textbf{(2)}</tex>
|}

Пусть <tex>\sigma</tex> {{---}} перестановка чисел <tex>\{0, ..., N\}</tex>, удовлетворяющая условию:
:{|
<tex>B_{\sigma(i)} \preceq B_{\sigma(i + 1)}</tex>, при <tex>i = 0, ..., N - 1\ \ \textbf{(3)}</tex>,
|}
и в случае равенства <tex>B_{\sigma(i)}</tex> и <tex>B_{\sigma(i + 1)}</tex> выполнено {{---}} <tex>\sigma(i) < \sigma(i + 1)</tex>. Перестановка однозначно определяется текстом <tex>B</tex> и ее можно посчитать за <tex>O(N)</tex>, используя сортировку подсчетом. Рассмотрим перестановку <tex>\sigma</tex> как отображение <tex>\sigma : \{0, ..., N\} \to \{0, ..., N\}</tex>. Пусть <tex>\sigma^{k}</tex> копмозиция <tex>k</tex> отображений <tex>\sigma^{k} = \sigma^{k - 1} \circ \sigma</tex>, где <tex>\sigma^{1} = \sigma, \sigma^{0} \equiv i</tex>.

{{Теорема
|statement=

''При всех <tex>m = 1, ..., N + 1</tex> верны утверждения,
:<tex>B_{\sigma(i)}...B_{\sigma^{m}(i)} \preceq B_{\sigma(i + 1)}...B_{\sigma^{m}(i + 1)}</tex>, при <tex>i = 0, ..., N - 1\ \ \textbf{(4)}</tex>
:<tex>B_iB_{\sigma(i)}...B_{\sigma^{m - 1}(i)} = S_{p(i) - 1}T[0..m - 1]</tex>, при <tex>i = 0, ..., N\ \ \textbf{(5)}</tex>
''

|proof=

Если лексикографически отсортировать буквы последнего столбца и поместить их в первый столбец, то получится таблица

| class="wikitable" style="text-align:center"
|-
!Таблица
|-
|a||b||c
|-
|a||b||c
|

}}

{{Теорема
|statement=

''Для восстановления исходного текста <tex>T</tex> из преобразования <tex>B</tex> достаточно знать число <tex>I</tex>, отвечающее условию <tex>p(I) = 0</tex>, другими словами <tex>S_{p(I)}T = T</tex>.''

}}

== Дополнительно ==

* bzip2 использует преобразование Барроуза {{---}} Уилера для превращения последовательностей многократно чередующихся символов в строки одинаковых символов, затем применяет преобразование MTF (англ. move-to-front), и в конце кодирование Хаффмана.

== Ссылки ==
*[http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%91%D0%B0%D1%80%D1%80%D0%BE%D1%83%D0%B7%D0%B0_%E2%80%94_%D0%A3%D0%B8%D0%BB%D0%B5%D1%80%D0%B0 Преобразование Барроуза {{---}} Уилера (Википедия)]

*[http://www.cs.karelia.ru/~aborod/inf/2010/schedule.php.ru Преобразование Барроуза {{---}} Уилера (cs.karelia.ru)]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Алгоритмы сжатия ]]

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

2013-12-04T12:23:22Z

94.26.129.35: /* Неограниченный рюкзак */

'''Задача о рюкзаке'''(''англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.

== Формулировка задачи ==

Дано <tex>N</tex> предметов, <tex>W</tex> - вместимость рюкзака, <tex>w=\{w_{1},w_{2},...,w_{N}\}</tex> — соответствующий ему набор положительных целых весов, <tex>p=\{p_{1},p_{2},...,p_{N}\}</tex> — соответствующий ему набор положительных целых стоимостей. Нужно найти набор бинарных величин <tex>B=\{b_{1},b_{2},...,b_{N}\}</tex>, где <tex>b_{i} = 1 </tex>, если предмет <tex>n_i</tex> включен в набор, <tex> b_{i} = 0 </tex>, если предмет <tex>n_i</tex> не включен, и такой что:

#<tex>b_{1} w_{1}+ ... + b_{N} w_{N} \le W</tex>
#<tex>b_{1} p_{1}+ ... + b_{N} p_{N} </tex> максимальна.

== Варианты решения ==

Задачу о рюкзаке можно решить несколькими способами:

* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.

* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}\times{N}) </tex>

* Метод динамического программирования. Сложность - <tex>O(N \times W)</tex>.

== Метод динамического программирования ==

Пусть <tex>A(k, s)</tex> есть максимальная стоимости предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,...,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.

<tex>A(k, 0) = 0</tex>

<tex>A(0, s) = 0</tex>

Найдем <tex>A(k, s)</tex>. Возможны 2 варианта:

#Если предмет <tex>k</tex> не попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex>, то есть <tex>A(k,s) = A(k-1, s)</tex>
# Если <tex>k</tex> попал в рюкзак. Тогда <tex>A(k, s)</tex> равно максимальной стоимости рюкзака, где вес <tex>s</tex> уменьшаем на вес <tex>k</tex> -ого предмета и набор допустимых предметов <tex>\{n_1,n_2,...,n_{k-1}\}</tex> плюс стоимость <tex>k</tex>, то есть <tex>A(k-1, s-w_k) + p_k</tex>

То есть:

#<tex>A(k,s) = A(k-1, s)</tex>
#<tex>A(k,s) = A(k-1, s-w_k) + p_k</tex>

Выберем из этих двух значений максимальное:

<tex>A(k,s) = max(A(k-1,s), A(k-1,s-w_{k}) + p_{k})</tex>

Стоимость искомого набора равна <tex>A(N,W)</tex>, так как нужно найти максимальную стоимость рюкзака, где все предметы допустимы и вместимость рюкзака <tex>W</tex>.

'''Восстановим набор предметов, входящих в рюкзак'''

Будем определять, входит ли <tex>n_i</tex> предмет в искомый набор. Начинаем с элемента <tex>A(i,w)</tex>, где <tex>i = N</tex>, <tex>w = W</tex>. Для этого сравниваем <tex>A(i,w)</tex> со следующими значениями:

#Максимальная стоимость рюкзака с такой же вместимостью и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex>, то есть <tex>A(i-1, w)</tex>
#Максимальная стоимость рюкзака с вместимостью на <tex>w_i</tex> меньше и набором допустимых предметов <tex>\{n_1,n_2,...,n_{i-1}\}</tex> плюс стоимость <tex>p_i</tex>, то есть <tex>A(i-1, w-w_i)+p_i</tex>

Заметим, что при построении <tex>A</tex> мы выбирали максимум из этих значений и записывали в <tex>A(i, w)</tex>. Тогда будем сравнивать <tex>A(i, w)</tex> c <tex>A(i-1, w)</tex>, если равны, тогда <tex>n_i</tex> не входит в искомый набор, иначе входит.

== Реализация ==
Сначала генерируем <tex>A</tex>.

for i = 0..W
A[0][i] = 0;
for i = 0..N
A[i][0] = 0; //Первые элементы приравниваем к 0
for k = 1..N
for s = 0..W //Перебираем для каждого k все вместисмости
if s >= w[k] //Если текущий предмет вмещается в рюкзак
A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]); //выбираем класть его или нет
else
A[k][s] = A[k-1][s]; //иначе, не кладем

Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:

findAns(k, s)
if A[k][s] == 0
return;
if A[k-1][s] == A[k][s]
findAns(k-1, s);
else
findAns(k-1, s - w[k]);
ans.push(k);

Сложность алгоритма <tex>O(N \times W)</tex>

== Пример ==

<tex>W = 13, N = 5</tex>

<tex>w_{1} = 3, p_{1} = 1 </tex>

<tex>w_{2} = 4, p_{2} = 6 </tex>

<tex>w_{3} = 5, p_{3} = 4 </tex>

<tex>w_{4} = 8, p_{4} = 7 </tex>

<tex>w_{5} = 9, p_{5} = 6 </tex>

[[Файл:Knapsack problem0.png]]

Числа от 0 до 13 в первой строчке обозначают вместимость рюкзака.

В первой строке как только вместимость рюкзака <tex>n \ge 3</tex>, добавляем в рюкзак 1 предмет.

Рассмотрим <tex>k = 3</tex>, при каждом <tex>s \ge 5 (</tex>так как <tex>w_3 = 5)</tex> сравниваем <tex>A[k-1][s]</tex> и <tex>A[k-1][s-w_3]+p_3</tex> и записываем в <tex>A[k][s]</tex> стоимость либо рюкзака без третьего предмета, но с таким же весом, либо с третьим предметом, тогда стоимость равна стоимости третьего предмета плюс стоимость рюкзака с вместимостью на <tex>w_3</tex> меньше.

Максимальная стоимость рюкзака находится в <tex>A(5, 13)</tex>.

'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''

Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ.

[[Файл:Задача о рюкзаке3.png]]

Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.

Стоимость рюкзака <tex>= 6 + 7 = 13</tex>

Вес рюкзака <tex>= 4 + 8 = 12</tex>

=Другие задачи семейства=
==Ограниченный рюкзак ==
'''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') - обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.

'''Пример:''' Вор грабит склад. Он может унести ограниченный вес, каждый товар на складе содержится в определенном ограниченном количестве. Нужно унести предметов на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран ограниченное <tex>b_i</tex> число раз.
Задача выбрать число <tex>x_i</tex> предметов каждого типа так, чтобы

* максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

* выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \in (0,1,...,b_i)</tex> для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
При небольших <tex>b_i</tex> решается сведением к классической задаче о рюкзаке. В иных случаях:
* Методом ветвей и границ.
* Методом динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого возможного числа предметов типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex>.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>d(i,c) = max(d(i - 1, c - lw_i) + lp_i) </tex> по всем целым <tex> l </tex> из промежутка <tex> 0 \le l \le min(b_i,\lfloor c/w_i \rfloor)</tex>.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного.

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

=== Реализация ===
for i = 0..W // база
d[0][i] = 0;
for i = 1..N
for c = 0..W //Перебираем для каждого i, все вместимости
d[i][c] = d[i - 1][c];
for l = min(b[i], c / w[i]) .. 1 // ищем l для которого выполняется максимум
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l);

Сложность алгоритма <tex>O(NW^2)</tex>.

==Неограниченный рюкзак==
'''Неограниченный рюкзак''' (англ.''Unbounded Knapsack Problem'') - обобщение ограниченного рюкзака, в котором любой предмет может быть выбран любое количество раз.

'''Пример:''' Перекупщик закупается на оптовой базе. Он может увезти ограниченное количество товара, количество товара каждого типа на базе не ограниченно. Нужно увезти товар на максимальную сумму.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i, c - w_i) + p_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = max(d(c), d(c - w_i) + p_i) </tex>;

Сложность алгоритма <tex>O(NW)</tex>.

==Непрерывный рюкзак==
'''Непрерывный рюкзак''' (англ. ''Continuous knapsack problem'') - вариант задачи, в котором возможно брать любою дробную часть от предмета, при этом удельная стоимость сохраняется.

'''Пример:''' Вор грабит мясника. Суммарно он может унести ограниченный вес товаров. Вор может резать товары без ущерба к удельной стоимости. Нужно унести товара на максимальную сумму.
===Формулировка Задачи===
Задача выбрать часть <tex>x_i</tex> каждого предмета так, чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N p_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

где <tex> 0 \le x_i \le 1</tex> дробное, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Возможность брать любую часть от предмета сильно упрощает задачу. Жадный алгоритм дает оптимальное решение в данном случае.

=== Реализация ===
sort(); // сортируем в порядке убывания удельной стоимости.
for i = 1..N // идем по предметам
if W >= w[i] //если помещается - берем
sum += p[i];
W -= w[i];
else
sum += W / w[i] * p[i];// иначе берем сколько можно и выходим
break;

==Задача о суммах подмножеств==
'''Задача о суммах подмножеств''' (англ. ''Subset-sum problem, Value Independent Knapsack Problem'') - задача из семейства, в которой стоимость предмета совпадает с его весом.

'''Пример:''' В машина может увезти определенное количество груза. Нужно увезти как можно больше крупного неделимого мусора за раз.
===Формулировка Задачи===
Нужно выбрать подмножество так, чтобы сумма ближе всего к <tex>W</tex>, но не превысила его. Формально, нужно найти набор бинарных величин <tex>x_i</tex>, так чтобы

*максимизировать общую стоимость: <tex>\sum_{i=1}^N w_ix_i</tex>;

*выполнялось условие совместности: <tex>\sum_{i=1}^N w_ix_i \le W</tex>;

<tex> x_j = 1 </tex> если <tex> j</tex> предмет назначен рюкзаку, иначе <tex> x_{ij} = 0 </tex>, для всех <tex> i= 1,2,...,N</tex>.

===Варианты решения===
Для решения пригодны любые методы применяемые для классической задачи, однако специализированые алгоритмы обычно более оптимальны по параметрам. Используются:
* Метод динамического программирования.
* Гибридный метод на основе динамического программирования и поиска по дереву. В худшем случае, работает за <tex> O(n) </tex>.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> максимальная сумма <tex>\le c</tex>, подмножества взятого из <tex> 1, ...,\ i</tex> элементов.

Заполним <tex>d(0,c)</tex> нулями.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
max(d(i - 1, c), d(i - 1, c - w_i) + w_i) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная сумма подмножества, не превышающая заданное значение.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача о размене==
'''Задача о размене''' (англ. ''Change-Making problem'') - имеются <tex> N </tex> неисчерпаемых типов предметов с весами <tex>w_i</tex>. Нужно наполнить рюкзак предметами с суммарным весом <tex>W</tex>.

Часто задачу ставят как, дать сдачу наименьшим количеством монет.
===Формулировка Задачи===
Каждый предмет может быть выбран любое число раз.
Задача выбрать количество <tex>x_i</tex> предметов каждого типа так, чтобы

*минимизировать количество взятых предметов: <tex>\sum_{i=1}^N x_i</tex>;

*сумма весов выбранных предметов равнялась вместимости рюкзака: <tex>\sum_{i=1}^N w_ix_i = W</tex>;

Где <tex> x_i \ge 0 </tex> целое, для всех <tex> i= 1,2,...,N</tex>.
===Варианты решения===
Самые распространенные методы точного решения это:
* Метод ветвей и границ.
* Метод динамического программирования.

===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> минимальное число предметов, типов от 1 до <tex>i</tex>, необходимое, чтобы заполнить рюкзак вместимостью <tex>c</tex>.

Пусть <tex>d(0,0) = 0</tex>, а <tex>d(0,c) = \inf</tex> для всех <tex>c > 0</tex>.

Тогда меняя i от 1 до <tex>N</tex>, рассчитаем на каждом шаге <tex>d(i,c)</tex>, для <tex>c</tex> от 0 до <tex>W</tex>, по рекуррентной формуле:

<tex>
d(i,c) =
\begin{cases}
d(i - 1, c) & for\ c = 0, ..., w_i - 1; \\
min(d(i - 1, c), d(i, c - w_i) + 1) & for\ c = w_i, ..., W;
\end{cases}
</tex>

После выполнения в <tex> d(N,W) </tex> будет лежать максимальная стоимость предметов, помещающихся в рюкзак.

Если не нужно восстанавливать ответ, то можно использовать одномерный массив <tex>d(c)</tex> вместо двумерного и использовать формулу:

<tex> d(c) = min(d(c), d(c - w_i) + 1) \qquad for\ c = w_i, ..., W</tex>.

Сложность алгоритма <tex>O(NW)</tex>.

==Задача об упаковке==
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') - имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно распределить все предметы, задействовав минимальное количество рюкзаков.

'''Пример:''' Нужно вывезти из шахты все куски руды, используя наименьшее число вагонеток.
===Формулировка Задачи===
Математически задачу можно представить так:

*минимизировать количество рюкзаков: <tex>\sum_{i=1}^N y_i</tex>;

*так чтобы выполнялось условие на совместность: <tex>\sum_{i=1}^N w_ix_{ij} \le Wy_j \qquad j \in {1, ..., N}</tex>;

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

<tex> y_i = 1 </tex> если <tex> i</tex> рюкзак используется. Иначе <tex> y_i = 0 </tex>.

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

==Мультипликативный рюкзак==
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') - есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.

'''Пример:''' У транспортной компании есть парк машин разной грузоподъемности. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременно.
===Формулировка Задачи===
Максимизировать <tex>\sum_{i=1}^M \sum_{j=1}^{N} p_jx_{ij}</tex>

так, чтобы <tex>\sum_{i=1}^N w_jx_{ij} \le W_i</tex> выполнялось для всех <tex> i= 1,2,...,N</tex>.

<tex>\sum_{j=1}^{M}x_{ij}=1</tex> для всех <tex> i= 1,2,...,N</tex>.

<tex> x_{ij} = 1 </tex> если <tex> j</tex> предмет назначен <tex>i </tex> рюкзаку. Иначе <tex> x_{ij} = 0 </tex>.

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

==Задача о назначении==
'''Задача о назначении''' (англ. ''Generalized Assignment Problem'') - Наиболее общая задача семейства. Отличается от мультипликативного рюкзака тем, что каждый предмет имеет различные характеристики в зависимости от рюкзака, куда его помещают. Есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\le N</tex>). У каждого рюкзака своя вместимость <tex>W_i</tex>, у <tex> j </tex> предмета <tex> p_{ij} </tex> стоимость и вес, при помещении его в <tex> i </tex> рюкзак, равны <tex> p_{ij} </tex> и <tex> w_{ij} </tex> соответственно. Задача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===

Максимизировать стоимость выбранных предметов <tex>\sum_{i=1}^M\sum_{j=1}^N p_{ij} x_{ij}</tex>,

при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \le W_i \qquad i=1, \ldots, M</tex>.

<tex> \sum_{i=1}^M x_{ij} \leq 1 \qquad j=1, \ldots, N</tex>.

<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.

===Варианты решения===
Применение динамического программирования нецелесообразно. Наиболее используем метод ветвей и границ.

= Литература =
*[http://informatics.mccme.ru/moodle/mod/book/view.php?id=815&chapterid=60 Дистанционная подготовка по информатике]
*[http://rosettacode.org/wiki/Knapsack_Problem Код для нескольких задач семейства на всевозможных языках]
*[http://www.diku.dk/users/pisinger/95-1.pdf David Pisinger Knapsack problems. — 1995]
*Silvano Martello, Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations — 1990 г. — ISBN 0-471-92420-2

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]