Изменения

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