子集和的快速解

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

还有一条评论说，它有可能使它“更有效率”。

多么?

此外，还有其他方法来解决这个问题，这些方法至少和上面的方法一样快吗？

编辑

我对任何可能导致加速的想法都感兴趣。我发现：

注:Pisinger09 09-2

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

编辑2

现在有一个后续行动：

用Pisinger快速求解子集和算法

Answer 1

我尊重你解决这个问题的快感！不幸的是，您是试图解决一个NP-完全的问题，这意味着任何突破多项式时间障碍的进一步改进都将是证明P= NP。

您从Hacker新闻中提取的实现似乎与伪多时间动态规划解一致，根据定义，任何其他改进都必须改进当前对该问题及其所有算法异构体的研究状况。换句话说:虽然持续加速是可能的，但在这个线程的上下文中，您不太可能看到这个解决方案的算法改进。

但是，如果需要具有可容忍错误程度的多时间解决方案，则可以使用使用近似算法。在维基百科公然窃取的伪码中，这将是：

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的进一步解读)

Answer 2

我不太了解python，但是有一种叫做meet in the中间的方法。伪码：

Divide activities into two subarrays, A1 and A2
for both A1 and A2, calculate subsets hashes, H1 and H2, the way You do it in Your question.
for each (cost, a1) in H1
     if(H2.contains(-cost))
         return a1 + H2[-cost];

这将使您能够在合理的时间内处理的活动元素数量翻一番。

Answer 3

我为“讨论”这个问题道歉，但是x值有界的“子集和”问题不是问题的NP版本。动态规划解是已知的有界x值问题。这是通过将x值表示为单位长度之和来实现的。动态规划解有许多与x的总长度呈线性关系的基本迭代，但是，当数字的精度等于N时，子集和以NP表示，即表示x's = N =N所需的数或基2的位置值为N= 40，x的个数必须为数十亿。在NP问题中，x的单位长度随N.That呈指数增长，这就是为什么动态规划解不是NP子集和问题的多项式时间解。在这种情况下，仍然存在子集和问题的实际例子，其中x是有界的，动态规划解是有效的。