16

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

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 的 Subset sum algorithm 的快速解决方案

4

6 回答 6

16

我尊重你试图解决这个问题的积极性!不幸的是,您正在尝试解决一个 NP-complete 问题,这意味着任何打破多项式时间障碍的进一步改进都将证明 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

于 2012-03-29T18:28:06.343 回答
7

我对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];

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

于 2012-03-26T12:04:48.547 回答
6

虽然我之前的回答描述了这个问题的多时间近似算法,但当x中的所有x i都是正数时,专门针对Pisinger 的多时间动态规划解决方案的实现提出了一个请求:

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 的这个子问题的最佳解决方案。

于 2012-03-31T03:24:33.880 回答
3

我为“讨论”这个问题道歉,但是 x 值有界的“子集总和”问题不是问题的 NP 版本。动态规划解决方案以有界 x 值问题而闻名。这是通过将 x 值表示为单位长度的总和来完成的。动态规划解决方案具有许多基本迭代,这些迭代与 x 的总长度成线性关系。但是,当数字的精度等于 N 时,子集总和为 NP。也就是说,表示 x 所需的数字或以 2 为底的位置值 = N。对于 N = 40,x 必须以十亿为单位。在 NP 问题中,x 的单位长度随 N 呈指数增长。这就是为什么动态规划解决方案不是 NP 子集和问题的多项式时间解决方案。既然如此,

于 2012-04-01T18:44:38.187 回答
2

以下是使代码更高效的三种方法:

  1. 该代码存储每个部分总和的活动列表。仅存储求和所需的最新活动,并在找到解决方案后通过回溯计算其余活动,在内存和时间方面更有效。

  2. 对于每个活动,字典都会重新填充旧内容(子集 [prev_sum] = 子集)。简单地增长一个字典更快

  3. 将值一分为二并在中间方法中应用相遇。

应用前两个优化会导致以下代码快 5 倍以上:

def subset_summing_to_zero2 (activities):
  subsets = {0:-1}
  for (activity, cost) in activities.iteritems():
      for prev_sum in subsets.keys():
          new_sum = prev_sum + cost
          if 0 == new_sum:
              new_subset = [activity]
              while prev_sum:
                  activity = subsets[prev_sum]
                  new_subset.append(activity)
                  prev_sum -= activities[activity]
              return sorted(new_subset)
          if new_sum in subsets: continue
          subsets[new_sum] = activity
  return []

同样应用第三个优化结果如下:

def subset_summing_to_zero3 (activities):
  A=activities.items()
  mid=len(A)//2
  def make_subsets(A):
      subsets = {0:-1}
      for (activity, cost) in A:
          for prev_sum in subsets.keys():
              new_sum = prev_sum + cost
              if new_sum and new_sum in subsets: continue
              subsets[new_sum] = activity
      return subsets
  subsets = make_subsets(A[:mid])
  subsets2 = make_subsets(A[mid:])

  def follow_trail(new_subset,subsets,s):
      while s:
         activity = subsets[s]
         new_subset.append(activity)
         s -= activities[activity]

  new_subset=[]
  for s in subsets:
      if -s in subsets2:
          follow_trail(new_subset,subsets,s)
          follow_trail(new_subset,subsets2,-s)
          if len(new_subset):
              break
  return sorted(new_subset)

定义 bound 为元素的最大绝对值。中间相遇方法的算法优势很大程度上取决于边界。

对于下限(例如 bound=1000 和 n=300),中间的相遇只得到了大约 2 倍的改进,而不是第一个改进的方法。这是因为称为子集的字典非常密集。

然而,对于一个上限(例如 bound=100,000 和 n=30),中间的相遇需要 0.03 秒,而第一个改进方法需要 2.5 秒(原始代码需要 18 秒)

对于上限,中间的相遇将取正常方法操作次数的平方根。

中间相遇的速度只是低界的两倍,这似乎令人惊讶。原因是每次迭代的操作数取决于字典中的键数。添加 k 个活动后,我们可能期望有 2**k 个键,但如果 bound 很小,那么这些键中的许多会发生冲突,因此我们将只有 O(bound.k) 个键。

于 2012-03-29T21:58:48.990 回答
0

以为我会为维基百科中描述的讨论的伪多时间算法分享我的 Scala 解决方案。这是一个稍作修改的版本:它计算出有多少个独特的子集。这与https://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers中描述的 HackerRank 问题非常相关。编码风格可能不是很好,我还在学习 Scala :) 也许这对某人仍然有帮助。

object Solution extends App {
    var input = "1000\n2"

    System.setIn(new ByteArrayInputStream(input.getBytes()))        

    println(calculateNumberOfWays(readInt, readInt))

    def calculateNumberOfWays(X: Int, N: Int) = {
            val maxValue = Math.pow(X, 1.0/N).toInt

            val listOfValues = (1 until maxValue + 1).toList

            val listOfPowers = listOfValues.map(value => Math.pow(value, N).toInt)

            val lists = (0 until maxValue).toList.foldLeft(List(List(0)): List[List[Int]]) ((newList, i) => 
                    newList :+ (newList.last union (newList.last.map(y => y + listOfPowers.apply(i)).filter(z => z <= X)))
            )

            lists.last.count(_ == X)        

    }
}
于 2014-04-07T17:51:21.720 回答