为了账号安全,请及时绑定邮箱和手机立即绑定

子集大小固定的总和子集

子集大小固定的总和子集

该款项子集的问题指出:给定一组整数,是否存在一个总和为零的非空子集?通常,此问题是NP完全的。我很好奇这个轻微变体的复杂性:给定一组整数,是否存在大小k和的总和为零的子集?例如,如果k = 1您可以进行二进制搜索以找到答案O(log n)。如果为k = 2,则可以将其简化为O(n log n)(例如,请参见从总和等于给定数的数组中查找一对元素)。如果为k = 3,则可以执行此操作O(n^2)(例如,请参见在数组中求和最接近给定数字的三个元素)。是否存在一个已知的界限可以作为函数来解决这个问题k?出于动机,我在考虑这个问题,如何将一个数组分成两部分,以使这两部分的平均值相等?并尝试确定它是否实际上是NP完整的。答案在于是否存在上述公式。除非有一般解决方案,否则我对了解的最佳界限会非常感兴趣k=4。
查看完整描述

3 回答

?
Qyouu

TA贡献1786条经验 获得超11个赞

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

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

诀窍是遍历所有索引,i并且j这种方式(a[i] + a[j])永远不会减少。并且对于kl(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)))。


查看完整回答
反对 回复 2019-11-28
  • 3 回答
  • 0 关注
  • 681 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信