Выберите числа, сумма которых равна нулю - PullRequest
Новая
       25

Выберите числа, сумма которых равна нулю

1 голос
/ 18 марта 2012

Существует N количество наборов, каждое из которых содержит различное количество целых чисел, например: 

(-2, -1, 0), (-1,4), (-2, 2, 3), (-3, -2, 4, 6), (-2)

Как выбрать ровно одно число из каждого набора, чтобы эти N целых суммировались в ноль?Например: 

-1, -1, 2, -2, 4, -2

Обратите внимание, что может не быть решения или множественного числа (в этом случае не имеет значения, какое я выберу).

Я думал, что могу сделать дыхание-сначала поиск, но мне было интересно, есть ли другие, желательно более быстрые, способы решить эту проблему.

Ответы [ 2 ]

1 голос
/ 18 марта 2012

Пусть dp[i, j] = true если мы можем сделать сумму j, используя одно число из каждого набора 1, 2, ..., i. 

dp[i, 0] = true for all i
for i = 1 to numSets do
  for num = 1 to sets[i].Count do
    for j = maxSum - sets[i, num] downto -maxSum do
      dp[i, j + sets[i, num]] |= dp[i - 1, j]

Вы можете использовать карту для обработки отрицательных индексов или добавить смещение ксделать их позитивными.maxSum - это максимальное значение, которое может принять ваша сумма (например, сумма максимумов всех наборов или сумма абсолютных значений минимумов, в зависимости от того, что больше).Могут быть способы обновления maxSum по мере оптимизации.

Для вашего примера это будет работать так: 

(-2, -1, 0), (-1,4), (-2, 2, 3), (-3, -2, 4, 6), (-2)

Итерация по первому набору даст dp[1, -2] = dp[1, -1] = dp[1, 0] = true.

Итерация за секунду даст dp[2, -3] = true (because dp[2, -2 + -1] |= dp[1, -1] = true), dp[2, -2] = true (because dp[2, -1 + -1] |= dp[1, -1] = true) и т. Д.

Если dp[numSets, 0] = true, есть решение, которое вы можете восстановить, отслеживая, какой последний номер вы выбраликаждый dp[i, j].

Сложность O(numSets * K * maxSum), где K - количество элементов набора.Это псевдополином.Это может быть достаточно быстро, если ваши значения невелики.Если ваши значения велики, но у вас мало наборов с небольшим количеством элементов, вам лучше использовать грубое отслеживание с помощью обратного отслеживания.

1 голос
/ 18 марта 2012

Похоже, это связано с проблемой суммы подмножеств : при заданном наборе n целых чисел существует ли подмножество с суммой 0?Известно, что эта проблема NP-complete , и это означает, что ваши шансы найти быстрый способ сделать это очень малы.

Для одного набора целых чисел достаточно сложнои в вашей задаче добавлено другое ограничение, что одно целое число должно быть выбрано из каждого набора.Алгоритм поиска - действительно правильный путь, но в худшем случае вы не добьетесь большего успеха, чем исчерпывающий поиск.

...