Сумма подмножества с двоичными числами

Я получил X двоичных чисел длины Y и хочу посмотреть, составляют ли они определенную сумму K.

Я провел небольшое исследование динамических решений для задач с суммой подмножеств; однако я думаю, что эта конкретная проблема представляет собой поворот.

Добавление двух двоичных чисел длиной Y и ограничение длины суммы до Y иногда приводит к вычитанию 2^(Y) из суммы (при переполнении). Поскольку добавление двух двоичных чисел иногда вызывает переполнение, например, добавление:

10000000000000000000000000000000000000010
10000000000000000000000000000000000000010

Принесет сумму

00000000000000000000000000000000000000100

Поэтому в некоторых случаях добавление чисел фактически уменьшит текущую сумму.

В данный момент я бьюсь головой о стену. Любые советы или указатели, как атаковать эту конкретную версию проблемы суммы подмножества?

ОБНОВИТЬ:

Нет никаких реальных ограничений на то, что я могу использовать. Моя единственная цель - создать максимально быстрое время выполнения с ~ 50 двоичными числами длиной ~ 40.


binary algorithm subset dynamic-programming subset-sum
person RasmusJ    schedule 26.12.2014    source источник
comment
Почему важно, как числа выражены? У вас есть еще некоторая версия проблемы суммы подмножества. Итак, каковы дополнительные ограничения, которые сделают его решаемым быстрее? Сколько чисел у вас может быть?   -  person Pradhan    schedule 26.12.2014
comment
Насколько я знаю, это не должно иметь значения, целые числа по модулю степени двойки представляют собой кольцо вместо поля, но ни один из алгоритмов суммирования подмножеств I знать о полагаться на существование мультипликативных инверсий.   -  person harold    schedule 26.12.2014
comment
Использование по модулю 2^(Y+1) не нарушит стандартный алгоритм динамического программирования?   -  person RasmusJ    schedule 26.12.2014
comment
Нет, но для этого потребуется массив длины 2^Y (кстати, разве это не по модулю 2^Y?)   -  person harold    schedule 26.12.2014
comment
Вы правы, это 2^Y. Однако массивы длиной 2 ^ Y, когда Y = ~ 40, в моем среднем случае выполнения кажутся экстремальными. Это единственное решение?   -  person RasmusJ    schedule 26.12.2014
comment
Вы можете попробовать наборы хэшей, так как большинство записей должны быть ложными. Или можно попробовать другой подход.   -  person harold    schedule 26.12.2014

Ответы (1)


arrow_upward
2
arrow_downward

Вы можете использовать технику встречи посередине.

  1. Разделите исходный массив на половинки (с 25 числами, если всего 50 чисел).

  2. Для каждой половины сгенерируйте все возможные суммы подмножеств (это занимает что-то вроде O(2^n) или O(2^n * n) времени). Это должно быть возможно для n = 25 (n - это размер половины).

  3. Для каждой возможной суммы из первой половины проверьте, есть ли соответствующая сумма во второй половине, используя хеш-таблицу (используя тот факт, что A + B = target (mod M) означает B = target - A (mod M)).

person kraskevich    schedule 26.12.2014
comment
Разве это не приведет к решению O (n ^ 2), которое также требует памяти O (n ^ 2)? Возможно, это единственный способ, но это не большой шаг вперед по сравнению с грубым решением (просто создание всех возможных подмножеств за время O (n ^ 2)). - person RasmusJ; 26.12.2014
comment
@RasmusJ Это O(2 ^ (n / 2)) время и память. Это намного лучше, чем O(2 ^ n). - person kraskevich; 26.12.2014