相关疑难解决方法(0)

我正在研究这个问题:

该子集和问题需要输入一个组X = {x1, x2 ,…, xn}的n整数和另一个整数K.问题是,以检查是否存在一个子集X'的X,它的元素之和为K,并发现该子集,如果有任何.例如,如果X = {5, 3, 11, 8, 2}和K = 16那么答案是YES,因为该子集X' = {5, 11}具有的总和16.实现Subset Sum的算法,其运行时间至少为O(nK).

注意复杂性O(nK).我认为动态编程可能有所帮助.

我找到了一个指数时间算法,但它没有帮助.

有人可以帮我解决这个问题吗？

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

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

最近我对子集求和问题产生了兴趣,该问题是在超集中找到零和子集.我在SO上找到了一些解决方案,此外,我遇到了一个使用动态编程方法的特定解决方案.我根据他的定性描述在python中翻译了他的解决方案.我正在尝试对更大的列表进行优化,这会占用大量的内存.有人可以推荐优化或其他技术来解决这个特殊问题吗？这是我在python中的尝试:

import random
from time import time
from itertools import product

time0 = time()

# create a zero matrix of size a (row), b(col)
def create_zero_matrix(a,b):
    return [[0]*b for x in xrange(a)]

# generate a list of size num with random integers with an upper and lower bound
def random_ints(num, lower=-1000, upper=1000):
    return [random.randrange(lower,upper+1) for i in range(num)]

# split a list up into N and P where N be the sum of the negative values and P …