Изменения

'''Meet-in-the-middle''' (Встреча в середине) — способ оптимизации

перебора. }}

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

Классической задачей является задача о наиболее эффективной упаковке рюкзака. Каждый предмет характеризуется весом (<tex> {w_{i} <= 10^{9}} </tex> ) и ценностью (<tex>{cost_{i} <= 10^{9}} </tex>). В рюкзак, ограниченный по весу, необходимо набрать вещей с максимальной суммарной стоимостью. Для ее решения изначальное множество вещей N разбивается на два равных(или примерно равных) подмножества, для которых за приемлемое время, можно перебрать все варианты и подсчитать суммарный вес и стоимость, а затем для каждого из них найти группу вещей из первого подмножества с максимальной стоимостью, укладывающуюся в ограничение по весу рюкзака. Сложность алгоритма <tex>O({2^{n/2}}\times{n})</tex>. Память <tex> O({2^{n/2}})</tex>