考虑这种方式解决的子集和问题：

Consider this way of solving the Subset sum problem:

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 []

我把它从这里：

I have it from here:

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

还有一个评论它说，有可能使更有效的。

There is also a comment which says that it is possible to make it "more efficient".

如何？

此外，是否有任何其他的方法来解决，它至少尽可能快地解决上述问题的一个？

Also, are there any other ways to solve the problem which are at least as fast as the one above?

修改

我感兴趣的任何想法，这将导致加速。我发现：

I'm interested in any kind of idea which would lead to speed-up. I found:

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

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

which mentions a linear time algorithm. But I don't have the paper, perhaps you, dear people, know how it works? An implementation perhaps? Completely different approach perhaps?

编辑2

现在有一个后续： Fast解决方案通过Pisinger 以子集和算法

There is now a follow-up: Fast solution to Subset sum algorithm by Pisinger

推荐答案

在我的previous答案描述< A HREF =htt​​ps://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm相对=nofollow>的polytime近似算法对这个问题，的是专门的提出的要求对于 Pisinger的polytime动态规划解决方案的实现，当所有的 X 我 的中的 X 的是积极的：

While my previous answer describes the polytime approximate algorithm to this problem, a request was specifically made for an implementation of Pisinger's polytime dynamic programming solution when all xi in x are positive:

from bisect import bisect

def balsub(X,c):
    """ Simple impl. of Pisinger's generalization of KP for subset sum problems
    satisfying xi >= 0, for all xi in X. Returns the state array "st", which may
    be used to determine if an optimal solution exists to this subproblem of SSP.
    """
    if not X:
        return False
    X = sorted(X)
    n = len(X)
    b = bisect(X,c)
    r = X[-1]
    w_sum = sum(X[:b])
    stm1 = {}
    st = {}
    for u in range(c-r+1,c+1):
        stm1[u] = 0
    for u in range(c+1,c+r+1):
        stm1[u] = 1
    stm1[w_sum] = b
    for t in range(b,n+1):
        for u in range(c-r+1,c+r+1):
            st[u] = stm1[u]
        for u in range(c-r+1,c+1):
            u_tick = u + X[t-1]
            st[u_tick] = max(st[u_tick],stm1[u])
        for u in reversed(range(c+1,c+X[t-1]+1)):
            for j in reversed(range(stm1[u],st[u])):
                u_tick = u - X[j-1]
                st[u_tick] = max(st[u_tick],j)
    return st

哇，那是头痛诱导。这需要校对，因为，虽然它实现 balsub ，我不能定义正确的比较，以确定是否该子问题SSP的最优解的存在。

Wow, that was headache-inducing. This needs proofreading, because, while it implements balsub, I can't define the right comparator to determine if the optimal solution to this subproblem of SSP exists.