28
правок
Изменения
Нет описания правки
Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsack()''' sn = <tex> \leftarrow </tex> N / 2, fn = <tex> \leftarrow </tex> N - sn; '''for ''' mask = 0 to <tex> \rightarrow </tex> 2 ** sn - 1 '''for ''' j = 0 to <tex> \rightarrow </tex> sn '''if ''' j-ый бит mask = 1 first[i].w += w[j]; first[i].c += cost[j]; '''sort'''(first); '''for ''' i = 0 to <tex> \rightarrow </tex> 2 ** sn - 1 '''if ''' (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c >= first[i].c) удалим множество с индексом i из массива first
Итоговое время работы <tex> {O({2^{N/2}}\times({N}+\log{2^{N/2}}))} = O({2^{N/2}}\times{N}) </tex>.