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