Проблема может быть решена в полиноме, если сумма элементов в наборе полиномиально связана с количеством элементов из вики:
Проблема может быть решена следующим образом
используя динамическое программирование. Предположим,
последовательность
x1, ..., xn
и мы хотим определить, есть ли
непустое подмножество, сумма которого равна 0. Пусть N
быть суммой отрицательных значений и
P сумма положительных значений.
Определить булевозначную функцию
Q (i, s) будет значением (true или false)
из
"there is a nonempty subset of x1, ..., xi which sums to s".
Таким образом, решение проблемы
значение Q (n, 0).
Ясно, Q (i, s) = false, если s
P, поэтому эти значения не нужно хранить или вычислять. Создать массив для
держать значения Q (i, s) для 1 ≤ i ≤ n
и N ≤ s ≤ P.
Теперь массив можно заполнить с помощью
простая рекурсия. Первоначально для N ≤ s
≤ P, установите
Q(1,s) := (x1 = s).
Тогда для i = 2,…, n, установите
Q(i,s) := Q(i − 1,s) or (xi = s) or Q(i − 1,s − xi) for N ≤ s ≤ P.
Для каждого присвоения значения Q
на правой стороне уже известны,
либо потому, что они были сохранены в
таблица для предыдущего значения I или
потому что Q (i - 1, s - xi) = false, если s -
xi P. Следовательно,
общее количество арифметических операций
является O (n (P - N)). Например, если все
Значения O (nk) для некоторого k, тогда
требуемое время O (nk + 2).
Этот алгоритм легко изменить на
вернуть подмножество с суммой 0, если есть
это один.
Это решение не считается
полиномиальное время в теории сложности
потому что P - N не является полиномом в
Размер проблемы, которая является
количество битов, используемых для его представления.
Этот алгоритм является полиномиальным в
значения N и P, которые являются
экспоненциальный по количеству бит.
Более общая проблема требует
суммирование подмножества до указанного значения
(не обязательно 0). Это можно решить
простой модификацией
алгоритм выше. Для случая, когда
каждый XI является положительным и ограничен
та же константа, Пизингер нашел линейный
алгоритм времени. [2]