Изменения
→Неограниченный рюкзак
{{Задача
|definition =
'''Задача о рюкзаке'''('' англ. Knapsack problem'') — дано <tex>N</tex> предметов, <tex>n_i</tex> предмет имеет массу <tex> w_i > 0</tex> и стоимость <tex> p_i > 0</tex>. Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины <tex>W</tex> (вместимость рюкзака), а суммарная стоимость была максимальна.
}}
* Перебирать все подмножества набора из N предметов. Сложность такого решения <tex>O({2^{N}})</tex>.
* Методом [[Meet-in-the-middle|Meet-in-the-middle]]. Сложность решения <tex> O({2^{N/2}}*{N}) </tex>
* Метод динамического программирования. Сложность — <tex>O(N*WNW)</tex>.
== Метод динамического программирования ==
Пусть <tex>A(k, s)</tex> есть максимальная стоимости стоимость предметов, которые можно уложить в рюкзак вместимости <tex>s</tex>, если можно использовать только первые <tex>k</tex> предметов, то есть <tex>\{n_1,n_2,\dots,n_k\}</tex>, назовем этот набор допустимых предметов для <tex>A(k,s)</tex>.
<tex>A(k, 0) = 0</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> не входит в искомый набор, иначе входит.
Метод динамического программирование всё равно не повзволяет позволяет решать задачу за полиномиальное время, потому что задача о ранце (или задача о рюкзаке) — одна из [[Класс NP|NP-полных]] задач комбинаторной оптимизации.
== Реализация ==
Сначала генерируем <tex>A</tex>.
'''for''' i = 0 '''to W''' w
A[0][i] = 0
'''for''' i = 0 '''to N''' n A[i][0] = 0 ''<font color="green">// Первые элементы приравниваем к 0</font>'' '''for''' k = 1 '''to N ''' n '''for''' s = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого k все вместимости</font>'' '''if''' s >= w[k] ''<font color="green">//Если текущий предмет вмещается в рюкзак</font>'' A[k][s] = max(A[k-1][s], A[k-1][s-w[k]]+p[k]) ''<font color="green">//выбираем Выбираем класть его или нет</font>''
'''else'''
A[k][s] = A[k-1][s] ''<font color="green">//иначеИначе, не кладем</font>''
Затем найдем набор <tex>ans</tex> предметов, входящих в рюкзак, рекурсивной функцией:
'''function''' findAns('''int''' k, '''int''' 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*WNW)</tex>
== Пример ==
'''Восстановление набора предметов, из которых состоит максимально дорогой рюкзак.'''
Начиная с <tex>A(5, 13)</tex> восстанавливаем ответ. Будем идти в обратном порядке по <tex>k</tex>. ''<font color="red000000">Красным обозначен фоном обозначим наш путь</font>''
{|border="1" class="wikitable" style="text-align:center" width="75%"
Таким образом, в набор входит <tex>2</tex> и <tex>4</tex> предмет.
Стоимость рюкзака : <tex>= 6 + 7 = 13</tex>
Вес рюкзака : <tex>= 4 + 8 = 12</tex>
=Другие задачи семейства=
==Ограниченный рюкзак =='''Ограниченный рюкзак''' (англ. ''Bounded Knapsack Problem'') — обобщение классической задачи, когда любой предмет может быть взят некоторое количество раз.
{{Задача
|definition =
}}
===Формулировка Задачи===
=== Реализация ===
'''for''' i = 0 '''to W ''' w ''<font color="green">// базаБаза</font>''
d[0][i] = 0
'''for''' i = 1 '''to N ''' n '''for''' c = 1 '''to W ''' w ''<font color="green">//Перебираем для каждого i, все вместимости </font>''
d[i][c] = d[i - 1][c]
'''for''' l = min(b[i], c / w[i]) to '''downto''' 1 ''<font color="green">//ищем Ищем l для которого выполняется максимум </font>''
d[i][c] = max(d[i][c], d[i - 1][c - l * w[i]] + p[i] * l)
Сложность алгоритма <tex>O(N*WNW^2)</tex>.
==Неограниченный рюкзак==
{{Задача
|definition =
}}
===Метод динамического программирования===
Пусть <tex>d(i,c)</tex> - максимальная стоимость любого количества вещей типов от 1 до <tex>i</tex>, суммарным весом до <tex>c</tex> включительно.
Заполним <tex>d(0,c)</tex> нулями.
==Непрерывный рюкзак==
{{Задача
|definition =
}}
=== Реализация ===
sort() ''<font color="green">// сортируем Сортируем в порядке убывания удельной стоимости.</font>'' '''for''' i = 1 '''to N ''' n ''<font color="green">// идем Идем по предметам </font>'' '''if''' W w > w[i] ''<font color="green">//если Если помещается — берем</font>'' sum += p[i] W w -= w[i] '''else''' sum += W w / w[i] * p[i] ''<font color="green">// иначе Иначе берем сколько можно и выходим</font>'' '''break'''
==Задача о суммах подмножеств==
{{Задача
|definition =
}}
==Задача об упаковке==
{{Задача
|definition =
'''Задача об упаковке''' (англ. ''Bin Packing Problem'') — имеются <tex> N </tex> рюкзаков вместимости <tex> W </tex> и столько же предметов с весами <tex>w_i</tex>. Нужно вывезти из шахты распределить все куски рудыпредметы, используя наименьшее число вагонетокзадействовав минимальное количество рюкзаков.
}}
==Мультипликативный рюкзак==
{{Задача
|definition =
'''Мультипликативный рюкзак''' (англ. ''Multiple Knapsack Problem'') — есть <tex>N</tex> предметов и <tex>M</tex> рюкзаков (<tex>M\leqslant N</tex>). У транспортной компании есть парк машин разной грузоподъемностикаждого рюкзака своя вместимость <tex>W_i</tex>. Нужно перевезти товара на максимальную сумму с одного склада на другой единовременноЗадача: выбрать <tex>M</tex> не пересекающихся множеств, назначить соответствие рюкзакам так, чтобы суммарная стоимость была максимальна, а вес предметов в каждом рюкзаке не превышал его вместимость.
}}
==Задача о назначении==
{{Задача
|definition =
}}
Весьма важная задача, так как она моделирует оптимальное распределение различных задач между вычислительными блоками.
===Формулировка Задачи===
при выполнении условия совместности <tex>\sum_{j=1}^N w_{ij} x_{ij} \leqslant W_i \qquad i=1, \ldots, M</tex>.
<tex> \sum_{i=1}^M x_{ij} \leq leqslant 1 \qquad j=1, \ldots, N</tex>.
<tex> x_{ij} \in \{0,1\} \qquad i=1, \ldots, N, \quad j=1, \ldots, N</tex>.
* [[Метод четырех русских для умножения матриц]]
* [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
* [[Meet-in-the-middle]]
== Источники информации ==