algorithm - 快速求解子集和

Question

考虑这种解决子集和问题的方法:

def subset_summing_to_zero (activities):
  subsets = {0: []}
  for (activity, cost) in activities.iteritems():
      old_subsets = subsets
      subsets = {}
      for (prev_sum, subset) in old_subsets.iteritems():
          subsets[prev_sum] = subset
          new_sum = prev_sum + cost
          new_subset = subset + [activity]
          if 0 == new_sum:
              new_subset.sort()
              return new_subset
          else:
              subsets[new_sum] = new_subset
  return []

我从这里得到它:

http://news.ycombinator.com/item?id=2267392

还有评论说可以让它“更有效率”。

如何？

另外，有没有其他方法可以至少与上述方法一样快地解决问题？

编辑

我对任何可以加快速度的想法都感兴趣。我发现:

https://en.wikipedia.org/wiki/Subset_sum_problem#cite_note-Pisinger09-2

其中提到了线性时间算法。但是我没有纸，亲爱的 friend ，也许你们知道它是如何工作的？也许是一个实现？也许是完全不同的方法？

编辑2

现在有后续:
Fast solution to Subset sum algorithm by Pisinger

Answer 1

我尊重您尝试解决此问题的敏捷性!不幸的是，你是trying to solve a problem that's NP-complete ，这意味着任何打破多项式时间障碍的进一步改进都将 prove that P = NP .

您从 Hacker News 中提取的实现似乎与 the pseudo-polytime dynamic programming solution 一致，根据定义，任何其他改进都必须推进当前对该问题及其所有算法异构体的研究状态。换句话说:虽然持续加速是可能的，但您非常不太可能在该线程的上下文中看到针对此问题的解决方案的算法改进。

但是，您可以 use an approximate algorithm如果您需要具有可容忍错误程度的多时间解决方案。在从维基百科公然窃取的伪代码中，这将是:

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 是目标总和

有关详细信息，请参阅 the Wikipedia article .

( Additional reference , further reading on CSTheory.SE )