标签: subset-sum

您将如何测试一组给定数字的所有可能的添加组合,以便它们加起来给定的最终数字？

例:

• 要添加的数字集:{1,5,22,15,0,...}
• 期望的结果:12345

我正在研究这个问题:

该子集和问题需要输入一个组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).我认为动态编程可能有所帮助.

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

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

在亚马逊采访中我问过这个问题 -

给定一个正整数数组,您必须找到无法从数组中的数字之和形成的最小正整数.

例:

Array:[4 13 2 3 1]
result= 11 { Since 11 was smallest positive number which can not be formed from the given array elements }

我做的是:

1. 排序数组
2. 计算前缀总和
3. 对求和数组进行求解并检查下一个元素是否小于1,即A [j] <=(sum + 1).如果不是这样,那么答案将是总和+ 1

但这是nlog(n)解决方案.

采访者对此并不满意,并在不到O(n log n)时间内提出解决方案.

我在接受采访时遇到了以下问题,尽管我提供了一个有效的实施方案,但效率还不够高.

数组A的切片是任意一对整数(P,Q),使得0≤P≤Q<N.如果数字A [P] + A [P,则数组A的切片(P,Q)可被K整除+1] + ... + A [Q-1] + A [Q]可被K整除.

要求我写的函数必须返回被K整除的切片数.预期的时间复杂度为O(max(N,K)),空间复杂度为O(K).

我的解决方案是最简单的,一个循环在另一个内部并检查每个切片:O(n ^ 2)

我一直在想,但我真的无法弄清楚如何在O(max(N,K))中做到这一点.

它可能是子集求和问题的变体,但我不知道如何计算每个子数组.

编辑:数组中的元素可能是否定的.这是一个例子:

A = {4, 5, 0, -2, -3, 1}, K = 5

Function must return 7, because there are 7 subarrays which sums are divisible by 5
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

我知道这可以通过对数组进行排序并获取更大的数字直到满足所需条件来完成.这至少需要nlog(n)的排序时间.

是否有任何改善nlog(n).

我们可以假设所有数字都是正数.

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

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

我有一个数字列表,例如

numbers = [1, 2, 3, 7, 7, 9, 10]

如您所见,数字可能会在此列表中出现多次.

我需要获得具有给定总和的这些数字的所有组合,例如10.

组合中的项目可以不重复,但是每个项目numbers必须被唯一地处理,这意味着例如7列表中的两个项目表示具有相同值的不同项目.

顺序是不重要的,所以[1, 9]和[9, 1]是相同的组合.

组合没有长度限制,[10]有效[1, 2, 7].

如何创建符合上述条件的所有组合的列表？

在这个例子中,它将是 [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

我正在寻找一种算法,它可以采用两组整数(正数和负数),并找到每个具有相同总和的子集.

问题类似于子集求和问题,除了我正在寻找两侧的子集.

这是一个例子:

列表A {4,5,9,10,1}

清单B {21,7,-4,180}

所以这里唯一的匹配是:{10,1,4,9} <=> {21,7,-4}

有谁知道这种问题是否存在现有的算法？

到目前为止,我所拥有的唯一解决方案是蛮力方法,它尝试每个组合,但它在指数时间内执行,我不得不对要考虑的元素数量设置硬限制,以避免花费太长时间.

我能想到的唯一其他解决方案是在两个列表上运行一个阶乘并寻找那里的等式,但这仍然不是很有效,并且随着列表变大而需要指数地增长.

我有一个与子集求和问题有关的问题,我想知道差异是否更容易,即在合理的时间内可解决.

给定一个值V,一个集合大小L和一个数字序列[1,N] S,S总和的多少个L子集总和小于V？

这与子集求和问题有三种不同:

1. 我关心有多少子集小于给定值,而不是有多少子集相等.
2. 子集大小是固定的.
3. 我关心有多少集合总和小于V,而不仅仅是否存在.

有没有合理有效的算法来解决这个问题？

编辑:显然,这可以使用组合生成算法在O(N选择L)中完成.我真正感兴趣的是聪明的黑客,以显着加快它的速度.

给定:整数数组值K,M

问题:找到我们可以从给定数组的所有K个元素子集中获得的最大总和,使得和小于值M？

是否存在可用于此问题的非动态编程解决方案？或者如果它只是dp [i] [j] [k]只能解决这类问题!你能解释一下算法吗？