Я уважаю готовность, с которой вы пытаетесь решить эту проблему! К сожалению, вы пытаетесь решить проблему, которая является NP-полной , что означает, что любое дальнейшее улучшение, которое преодолеет полиномиальный временной барьер, докажет, что P = NP .
Реализация, которую вы извлекли из Hacker News, похоже, согласуется с решением для динамического программирования с псевдополимедией , где любые дополнительные улучшения должны, по определению, улучшать состояние текущих исследований этой проблемы и все его алгоритмические изоформы. Другими словами: хотя возможно постоянное ускорение, вы очень вряд ли увидите алгоритмическое улучшение этого решения проблемы в контексте этой цепочки.
Однако, вы можете использовать приблизительный алгоритм , если вам требуется решение на основе множителя с допустимой степенью ошибки. В псевдокоде, явно украденном из Википедии, это будет:
initialize a list S to contain one element 0.
for each i from 1 to N do
let T be a list consisting of xi + y, for all y in S
let U be the union of T and S
sort U
make S empty
let y be the smallest element of U
add y to S
for each element z of U in increasing order do
//trim the list by eliminating numbers close to one another
//and throw out elements greater than s
if y + cs/N < z ≤ s, set y = z and add z to S
if S contains a number between (1 − c)s and s, output yes, otherwise no
Реализация Python, максимально сохраняющая исходные термины:
from bisect import bisect
def ssum(X,c,s):
""" Simple impl. of the polytime approximate subset sum algorithm
Returns True if the subset exists within our given error; False otherwise
"""
S = [0]
N = len(X)
for xi in X:
T = [xi + y for y in S]
U = set().union(T,S)
U = sorted(U) # Coercion to list
S = []
y = U[0]
S.append(y)
for z in U:
if y + (c*s)/N < z and z <= s:
y = z
S.append(z)
if not c: # For zero error, check equivalence
return S[bisect(S,s)-1] == s
return bisect(S,(1-c)*s) != bisect(S,s)
... где X - ваш пакет терминов, c - ваша точность (от 0 до 1), а s - целевая сумма.
Подробнее см. статья в Википедии .
( Дополнительная справка , дальнейшее чтение на CSTheory.SE )