3622
правки
Изменения
м
'''sort'''(sum, key = "res") // сортируем sum по полю res
Нет описания правки
=== Реализация ===
// sum - массив сумм a + b, cnt - счетчик массива sum
'''findsum'''():
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
sum[cnt].b = b
cnt++
'''for''' c = 0..N - 1
'''for''' d = 0..N - 1
Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsack'''():
sn = N / 2
fn = N - sn
'''for''' mask = 0..2 ** sn - 1
'''for''' j = 0 .. sn
'''if''' j-ый бит mask == 1
first[i].w += w[j];
first[i].c += cost[j]
сортируем first по весу
'''for''' i = 0 .. 2 ** sn - 1 '''if''' существует такое подмножество с индексом j, что first[j].w <tex> \leqslant </tex> first[i].w && '''and''' first[j].c <tex> \geqslant </tex> first[i].c
удалим множество с индексом i из массива first
index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv
'''if''' first[index].w <tex> \leqslant </tex> R - curw && '''and''' first[index].c + curcost <tex> > </tex> ans
ans = first[index].c + curcost
'''return''' ans
