Изменения

Meet-in-the-middle

24 байта убрано, 20:44, 22 декабря 2012

Нет описания правки

sum[cnt].b = b

cnt++

~~// сортируем sum по полю res~~ '''sort'''(sum, key="res") // сортируем sum по полю res

'''for''' c = 0..N - 1

'''for''' d = 0..N - 1

first[i].w += w[j];

first[i].c += cost[j];

// сортируем first по весу ~~'''sort'''(first);~~

'''for''' i = 0 .. 2 ** sn - 1

'''if''' (существует такое подмножество с индексом j, что first[j].w <= first[i].w && first[j].c >= first[i].c)

удалим множество с индексом i из массива first

index = позиция, найденная бинарным поиском в массиве first, подмножества с максимальным весом, не превыщающим R - curv

'''if''' (first[index].w <= R - curw && first[index].c + curcost > ans)

ans = first[index].c + curcost

'''return''' ans

3622

правки