3622
правки
Изменения
м
Нет описания правки
== Задача о нахождение четырех чисел с суммой равной нулю ==
Дан массив целых чисел <tex>{A}</tex>. Требуется найти любые '''<tex> 4''' </tex> числа, сумма которых равна '''<tex> 0''' </tex> (одинаковые элементы могут быть использованы несколько раз).
Например : <tex> {A} = ({2,3,1,0,-4,-1}) </tex>. Решением данной задачи является, например, четверка чисел <tex> 3 + 1 + 0 - 4 = 0</tex> или <tex> 0 + 0 + 0 + 0 = 0</tex>.
=== Реализация ===
// sum - массив сумм a + b, cnt - счетчик массива sum
'''findsum'''():
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
sum[cnt].b = b
cnt++
'''sort'''(sum, key="res") // сортируем sum по полю res
'''for''' c = 0..N - 1
'''for''' d = 0..N - 1
'''return''' "No solution"
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.
Если вместо отсортированного массива использовать [[Хеш-таблица | хэш-таблицу]], то задачу можно будет решить за время <tex> O(N^2) </tex>.
== Задача о рюкзаке ==
Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} \le leqslant 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} \le leqslant 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{N/2}}\timescdot{N})</tex>. Память <tex> O({2^{N/2}})</tex>.
=== Реализация ===
Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsack'''():
sn = N / 2
fn = N - sn;
'''for''' mask = 0..2 ** sn - 1
'''for''' j = 0 .. sn
'''if''' j-ый бит mask == 1
first[i].w += w[j];
first[i].c += cost[j];
сортируем first по весу
'''for''' i = 0 .. 2 ** sn - 1
'''if''' существует такое подмножество с индексом j, что first[j].w <= tex> \leqslant </tex> first[i].w && first[j].c <tex> \geqslant </tex>= first[i].c
удалим множество с индексом i из массива first
'''for''' mask = 0..2 ** fn - 1
'''for''' j = 0..fn
'''if''' j-ый бит mask == 1 curw += w[j + sn]; curcost += cost[j + sn];
index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv
'''if''' first[index].w <= tex> \leqslant </tex> R - curw && first[index].c + curcost > ans
ans = first[index].c + curcost
'''return''' ans
Итоговое время работы <tex> {O({2^{N/2}}\timescdot({N}+\log{2^{N/2}}))} = O({2^{N/2}}\times{N}) </tex>.
== Задача о нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая '''Meet-in-the-middle''' — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает <tex> N </tex>.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояния у нас есть '''<tex> K''' </tex> переходов, тогда бы мы сгенерировали <tex> {K^{N}} </tex> состояний. Асимптотика данного решения составила бы <tex> {O({K^{N}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{N/2}})} </tex>. <br>
=== Алгоритм решения ===
