33

和子集问题指出：

给定一组整数，是否存在总和为零的非空子集？

这个问题通常是NP完全的。我很好奇这种轻微变体的复杂性是否已知：

给定一组整数，是否存在k总和为零的大小子集？

例如，如果k = 1，您可以进行二分搜索以在 中找到答案O(log n)。如果k = 2，那么您可以将其归结为O(n log n)（例如，请参阅从总和等于给定数字的数组中查找一对元素）。如果k = 3，那么您可以这样做O(n^2)（例如，请参阅在数组中查找三个元素，其总和最接近给定数字）。

是否有一个已知的界限可以作为这个问题的函数k？

作为动机，我在考虑这个问题如何将数组分成两部分，使两部分的平均值相等？并试图确定它是否实际上是 NP 完全的。答案在于是否存在上述公式。

除非有一个通用的解决方案，否则我很想知道k=4.

4

6 回答 6

16

对于k=4，空间复杂度O(n)，时间复杂度O(n 2 * log(n))

对数组进行排序。从 2 个最小和 2 个最大的元素开始，按非递减顺序计算所有lesser2 个元素的总和，并按非递增顺序计算所有 2 个元素的总和。如果总和小于零，则增加总和，如果总和大于零，则减少一，当总和为零（成功）或（失败）时停止。(a[i] + a[j])greater(a[k] + a[l])lessergreatera[i] + a[j] > a[k] + a[l]

诀窍是遍历所有索引i，并且j以一种(a[i] + a[j])永远不会减少的方式。而对于k和l，(a[k] + a[l])永远不应该增加。优先级队列有助于做到这一点：

  1. 放入key=(a[i] + a[j]), value=(i = 0, j = 1)优先队列。
  2. (sum, i, j)从优先队列中弹出。
  3. sum在上述算法中使用。
  4. (a[i+1] + a[j]), i+1, j仅(a[i] + a[j+1]), i, j+1当这些元素尚未使用时才放入优先级队列。要跟踪使用过的元素，请为每个“i”维护一个最大使用过的“j”数组。仅使用大于“i”的“j”值就足够了。
  5. 从步骤 2 继续。

对于 k>4

如果空间复杂度限制为 O(n)，我找不到比对k-4值使用蛮力和对剩余4值使用上述算法更好的方法。时间复杂度 O(n (k-2) * log(n))。

对于非常大的k 整数线性规划可能会带来一些改进。

更新

如果n非常大（与最大整数值相同的顺序），则可以实现 O(1) 优先级队列，将复杂性提高到 O(n 2 ) 和 O(n (k-2) )。

如果n >= k * INT_MAX，则具有 O(n) 空间复杂度的不同算法是可能的。为所有可能的值总和预先计算一个位集k/2。并用它来检查其他k/2值的总和。时间复杂度为 O(n (ceil(k/2)) )。

于 2012-01-19T13:03:31.690 回答
4

W + X + Y + Z = {w + x + y + z | 中是否为0的问题 w 中的 w，X 中的 x，Y 中的 y，Z 中的 z} 基本相同，除了没有烦人的退化情况（即，这些问题可以用最少的资源相互简化）。

这个问题（因此 k = 4 的原始问题）具有 O(n^2 log n)-时间、O(n)-空间算法。k = 2 的 O(n log n) 时间算法（以确定 A + B 中是否为 0）以排序顺序访问 A，以反向排序顺序访问 B。因此，我们只需要一个 A = W + X 的 O(n) 空间迭代器，它可以对称地重复用于 B = Y + Z。让 W = {w1, ..., wn} 按排序顺序。对于 X 中的所有 x，将键值项 (w1 + x, (1, x)) 插入优先级队列。重复删除最小元素 (wi + x, (i, x)) 并插入 (wi+1 + x, (i+1, x))。

于 2012-01-19T04:44:25.123 回答
3

以 awesomo 的答案为基础......如果我们可以假设数字是排序的，对于给定的 k，我们可以做得比 O(n^k) 更好；只需取所有大小为 (k-1) 的 O(n^(k-1)) 子集，然后在剩余的部分中进行二分搜索，找到一个数字，当添加到第一个 (k-1) 时，给出目标。这是 O(n^(k-1) log n)。这意味着复杂性肯定低于此。

事实上，如果我们知道 k=3 的复杂度为 O(n^2)，我们可以在 k > 3 时做得更好：选择所有 (k-3)-子集，其中有 O(n^( k-3))，然后在剩余元素上解决 O(n^2) 中的问题。对于 k >= 3，这是 O(n^(k-1))。

但是，也许你可以做得更好？我会考虑这个的。

编辑：我最初打算添加很多建议对这个问题提出不同的看法，但我决定发布一个删节版。我鼓励其他发帖者看看他们是否认为这个想法有任何价值。分析很困难，但它可能已经足够疯狂了。

我们可以利用我们有一个固定的 k 以及奇数和偶数之和以某种方式表现这一事实来定义一个递归算法来解决这个问题。

首先，修改问题，以便在列表中同时包含偶数和奇数（如果全部为偶数，则可以通过除以 2 来完成，或者如果全部为奇数，则从数字中减去 1 并从目标总和中减去 k，然后重复有必要的）。

接下来，利用只有使用偶数个奇数才能达到偶数目标和的事实，并且仅使用奇数个奇数才能达到奇数目标和。生成适当的奇数子集，并使用偶数递归调用算法，总和减去被检查的奇数子集的总和，k 减去奇数子集的大小。当 k = 1 时，进行二分查找。如果曾经 k > n（不确定这是否会发生），则返回 false。

如果您的奇数很少，这可以让您非常快速地选择必须是获胜子集的一部分的术语，或者丢弃不能的术语。您可以使用减法技巧将具有大量偶数的问题转换为具有大量奇数的等效问题。因此，最坏的情况一定是偶数和奇数的数量非常相似......这就是我现在所处的位置。一个无用的宽松上限比蛮力差很多数量级，但我觉得这可能至少与蛮力一样好。欢迎提出想法！

EDIT2：上面的一个例子，用于说明。

{1, 2, 2, 6, 7, 7, 20}, k = 3, sum = 20.
Subset {}:
 {2, 2, 6, 20}, k = 3, sum = 20
 = {1, 1, 3, 10}, k = 3, sum = 10
 Subset {}:
  {10}, k = 3, sum = 10
  Failure
 Subset {1, 1}:
  {10}, k = 1, sum = 8
  Failure
 Subset {1, 3}:
  {10}, k = 1, sum = 6
  Failure
Subset {1, 7}:
 {2, 2, 6, 20}, k = 1, sum = 12
 Failure
Subset {7, 7}:
 {2, 2, 6, 20}, k = 1, sum = 6
 Success
于 2012-01-18T21:46:44.467 回答
3

O(n^2log(n)) 中 k=4 的解

步骤 1：计算成对和并对列表进行排序。有 n(n-1)/2 个和。所以复杂度是O(n^2log(n))。保留进行总和的个人的身份。

第 2 步：为上述列表中的每个元素搜索补集，并确保它们不共享“个体”。有 n^2 次搜索，每个搜索的复杂度为 O(log(n))

编辑：原始算法的空间复杂度为 O(n^2)。空间复杂度可以通过模拟一个虚拟 2D 矩阵（O(n)，如果你考虑空间来存储数组的排序版本）减少到 O(1)。

首先关于 2D 矩阵：对数字进行排序并使用成对求和创建矩阵 X。现在矩阵是这样一种方式，即所有的行和列都被排序。要在此矩阵中搜索一个值，请搜索对角线上的数字。如果数字在 X[i,i] 和 X[i+1,i+1] 之间，则基本上可以将搜索空间减半为矩阵 X[i:N, 0:i] 和 X[0:i ， 在]。结果搜索算法为 O(log^2n)（我不太确定。有人可以检查吗？）。

现在，不是使用实矩阵，而是使用虚拟矩阵，其中 X[i,j] 是根据需要计算的，而不是预先计算它们。

结果时间复杂度：O( (nlogn)^2 )。

PS：在下面的链接中，它说二维排序矩阵搜索的复杂度是 O(n) 复杂度。如果这是真的（即 O(log^2n) 不正确），那么最终的复杂度是 O(n^3)。

于 2012-01-18T21:47:49.963 回答
2

非常相似的问题：

子集和问题的这个变体更容易解决吗？

它仍然是NP完全的。

如果不是，则子集和也将在 P 中，因为它可以表示为F(1) | F(2) | ... F(n)F 是您的函数。这O(O(F(1)) + O(F(2)) + O(F(n)))将仍然是多项式，这是不正确的，因为我们知道它是 NP 完全的。

请注意，如果您对输入有一定的限制，则可以实现多项式时间。

另请注意，可以使用二项式系数计算蛮力运行时间。

于 2012-01-18T21:40:01.297 回答
0

时间复杂度是微不足道O(n^k)的（k来自n元素的大小子集的数量）。

由于k是一个给定的常数，一个（可能是相当高阶的）多项式上限将复杂度作为 的函数n。

于 2012-01-18T20:16:03.567 回答