28
правок
Изменения
Нет описания правки
for j = 0 to fn
if j-ый бит mask = 1
curw += w[j+ sn]; curcost += cost[j+ sn];
p = findmax(); // Находим маску вещей из первой половины с макcимальной стоимостью и подходящей по весу
if (curw + first[p].w < = R && curcost + first[p].c > ans) ans = curcost + first[p].c;
print ans
== Задача о нахождение нахождении кратчайшего расстояния между двумя вершинами в графе ==
[[Файл:bfs.png|600px|thumb|right|Нахождение кратчайшего расстояния между двумя вершинами]]
Еще одна задача, решаемая алгоритмом Meet-in-the-middle — это нахождение кратчайшего расстояния между двумя вершинами, зная начальное состояние, конечное состояние и то, что длина оптимального пути не превышает '''N'''.
Стандартным подходом для решения данной задачи, является применение алгоритма [[Обход в ширину|обхода в ширину]]. Пусть из каждого состояние состояния у нас есть '''K''' переходов, тогда бы мы сгенерировали <tex> {K^{n}} </tex> состояний. Асимптотика данного рещения решения составила бы <tex> {O({K^{n}})} </tex>. '''Meet-in-the-middle''' помогает снизить асимптотику до <tex> {O({K^{n/2}})} </tex>. <br>
=== Алгоритм решения ===
