Если вы правильно измените алгоритм Горовица-Сахни, то он вряд ли будет медленнее, чем оригинальный Горовиц-Сахни.Напомним, что Горовиц-Сахни работает с двумя списками сумм подмножеств: суммы подмножеств в левой половине исходного списка и суммы подмножеств в правой половине.Вызовите эти два списка сумм L и R. Чтобы получить подмножества, которые суммируют с некоторым фиксированным значением A, вы можете отсортировать R, а затем найти число в R, соответствующее каждому числу в L, используя двоичный поиск.Однако алгоритм асимметричен только для сохранения постоянного фактора в пространстве и времени.Для этой проблемы неплохо бы отсортировать и L, и R.
. В моем коде ниже я также обращаюсь к L. Затем вы можете сохранить два указателя на R, обновленные для каждой записи в L: указатель на последнийслишком низкая запись в R, а указатель на первую запись в R слишком высокий.Когда вы переходите к следующей записи в L, каждый указатель может либо двигаться вперед, либо оставаться на месте, но им не придется двигаться назад.Таким образом, второй этап алгоритма Горовица-Сахни занимает только линейное время в данных, сгенерированных на первом этапе, плюс линейное время в длине вывода.Вплоть до постоянного фактора, вы не можете добиться большего успеха, чем это (как только вы посвятите себя этому алгоритму встречи посередине).
Вот код Python с примером ввода:
# Input
terms = [29371, 108810, 124019, 267363, 298330, 368607,
438140, 453243, 515250, 575143, 695146, 840979, 868052, 999760]
(A,B) = (500000,600000)
# Subset iterator stolen from Sage
def subsets(X):
yield []; pairs = []
for x in X:
pairs.append((2**len(pairs),x))
for w in xrange(2**(len(pairs)-1), 2**(len(pairs))):
yield [x for m, x in pairs if m & w]
# Modified Horowitz-Sahni with toolow and toohigh indices
L = sorted([(sum(S),S) for S in subsets(terms[:len(terms)/2])])
R = sorted([(sum(S),S) for S in subsets(terms[len(terms)/2:])])
(toolow,toohigh) = (-1,0)
for (Lsum,S) in reversed(L):
while R[toolow+1][0] < A-Lsum and toolow < len(R)-1: toolow += 1
while R[toohigh][0] <= B-Lsum and toohigh < len(R): toohigh += 1
for n in xrange(toolow+1,toohigh):
print '+'.join(map(str,S+R[n][1])),'=',sum(S+R[n][1])
«Идиот» (думаю, ему следует сменить имя пользователя) поднимает разумную проблему оптимизации алгоритма, пропуская один из видов.На самом деле, поскольку каждый список L и R является списком размеров подмножеств, вы можете выполнить комбинированную генерацию и сортировку каждого из них за линейное время!(То есть, линейные по длинам списков.) L - это объединение двух списков сумм, тех, которые включают первый член, член [0], и тех, которые не имеют.Так что на самом деле вы должны просто сделать одну из этих половин в отсортированном виде, добавить константу, а затем выполнить слияние двух отсортированных списков.Если вы примените эту идею рекурсивно, вы сохраните логарифмический фактор во времени, чтобы создать отсортированный L, то есть фактор N в исходной переменной задачи.Это дает хорошую причину для сортировки обоих списков по мере их создания.Если вы сортируете только один список, у вас есть несколько бинарных поисков, которые могут снова ввести этот коэффициент N;в лучшем случае вы должны как-то оптимизировать их.
На первый взгляд, коэффициент O (N) все еще может быть там по другой причине: если вы хотите не просто сумму подмножества, а подмножество, которое делаетсуммируя, тогда выглядит как O (N) время и пространство для хранения каждого подмножества в L и в R. Тем не менее, существует прием обмена данными, который также избавляет от этого фактора O (N).Первым шагом хитрости является сохранение каждого подмножества левой или правой половины в виде связанного списка битов (1, если термин включен, 0, если он не включен).Затем, когда список L удваивается по размеру, как в предыдущем абзаце, два связанных списка для подмножества и его партнера могут совместно использоваться, за исключением заголовка:
0
|
v
1 -> 1 -> 0 -> ...
На самом деле этот трюк со связанным спискомявляется артефактом модели затрат и никогда по-настоящему не помогает.Потому что для того, чтобы указатели в архитектуре ОЗУ стоили O (1), вы должны определить слова данных с битами O (log (memory)).Но если у вас есть слова данных такого размера, вы можете также хранить каждое слово как один битовый вектор, а не с этой структурой указателя.То есть, если вам нужно меньше гигаворда памяти, вы можете хранить каждое подмножество в 32-битном слове.Если вам нужно больше, чем гигаворд, у вас есть 64-битная архитектура или ее эмуляция (или, может быть, 48 бит), и вы все равно можете хранить каждое подмножество в одном слове.Если вы исправите модель стоимости ОЗУ, чтобы учесть размер слова, то этот фактор N так или иначе никогда не существовал.
Итак, что интересно, сложность времени для оригинального алгоритма Горовица-Сахни не равна O (N * 2 ^ (N / 2)), это O (2 ^ (N / 2)).Аналогично, сложность по времени для этой задачи составляет O (K + 2 ^ (N / 2)), где K - длина вывода.