相关疑难解决方法(0)

NP,NP-Complete和NP-Hard有什么区别？

我知道网上有很多资源.我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道.

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

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快速解决子集和算法