84
правки
Изменения
Нет описания правки
=== Реализация ===
// sum - массив сумм a + b, cnt - счетчик массива sum
'''function'''findsum('''int[]'''(A):
'''for''' a = 0..N - 1
'''for''' b = 0..N - 1
sum[cnt].res = A[a] + BA[b]
sum[cnt].a = a
sum[cnt].b = b
'''for''' c = 0..N - 1
'''for''' d = 0..N - 1
'''if''' сумма -(A[c] + A[d]) есть в массив sum
index = индекс суммы -(A[c] + A[d])
'''return''' (sum[index].a, sum[index].b, A[c], A[d])
Реализуем данный алгоритм:
// N - количество всех вещей, w[] - массив весов всех вещей, cost[] - массив стоимостей всех вещей, R - ограничение по весу рюкзака.
'''knapsackfunction'''knapsack():'''int'''
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]
sort(first, key = "w") // сортируем 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
'''for''' mask = 0..2 ** fn - 1
'''for''' j = 0..fn
curw += w[j + sn]
curcost += cost[j + sn]
index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv
'''if''' first[index].w <tex> \leqslant </tex> R - curw '''and''' first[index].c + curcost <tex> > </tex> ans
* [[Целочисленный двоичный поиск]]
==CсылкиИсточники информации==
*[http://infoarena.ro/blog/meet-in-the-middle Meet-in-the-middle]
*[http://g6prog.narod.ru/dpl.ps Лекции по информатике (36 страница)]
