Я работаю над этой проблемой:
Задача Subset Sum принимает на вход набор
X = {x1, x2 ,…, xn}
целых чиселn
и другое целое числоK
. Проблема состоит в том, чтобы проверить, существует ли подX'
подмножествоX
, элементы которого суммируются доK
и находит подмножество, если оно есть. Например, еслиX = {5, 3, 11, 8, 2}
иK = 16
, тогда ответ будетYES
, так как подмножествоX' = {5, 11}
имеет сумму16
. Реализовать алгоритм подмножества Sum, время выполнения которого не менееO(nK)
.
Сложность уведомления O(nK)
. Я думаю, что динамическое программирование может помочь.
Я нашел алгоритм экспоненциального времени, но это не помогает.
Может кто-нибудь помочь мне решить эту проблему?