快速解决子集和

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

提到线性时间算法.但我没有纸,也许你,亲爱的人,知道它是如何运作的吗？也许是一个实现？也许完全不同的方法？

编辑2

现在有一个跟进:
Pisinger快速解决子集和算法

Answer 1

我尊重你试图解决这个问题的快感!不幸的是,你试图解决一个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是目标总和.

有关更多详细信息,请参阅Wikipedia文章.

(补充参考,进一步阅读CSTheory.SE)

Answer 2

我不太了解python,但在中间有一种叫做meet的方法.伪代码:

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

虽然我以前的答复介绍了polytime近似算法对这个问题,要求被专门为一个实现方式制成Pisinger的polytime动态规划的解决方案时,所有的X _我在X是积极的:

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子问题的最优解.