Изменения

'''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

'''for ''' mask = 0 to <tex> \rightarrow </tex> 2 ** fn - 1 '''for ''' j = 0 to <tex> \rightarrow </tex> fn '''if ''' j-ый бит mask = 1 curw += w[j + sn]; curcost += cost[j + sn];

В массиве first бинарным поиском находим подмножество, с максимальным весом, который не превышает R - curw '''if ''' (first[index].w <= R - curw && first[index].c + curcost > ans) ans = first[index].c + curcost print '''return''' ans