超过给定值的子数组中最小的和

Question

超过给定值的子数组中最小的和

arraysalgorithmperformancenumbers

4

输入: 一个由N个正数和一个值为X的数组，其中N相对于X较小。
输出: 子数组，其所有数字之和等于Y > X，且没有其他子数组的数字之和大于X但小于Y。

这个问题是否有多项式解法？如果有，你能呈现出来吗？

- Ilya Gazman

你的数组元素有限制吗？ - sve

子数组的值是否必须在较大的数组中相邻？解决方案是否唯一并不重要吗？ - Jeff Irwin

通常情况下不行。但是如果有帮助的话，您可以将它们限制为无重复项、正值和小于10^10。 - Ilya Gazman

O(X*Y) 可以接受吗？ - sve

@JeffIrwin 可能有多个等于 Y 的解决方案，我会满足于找到其中任意一个。而且结果子数组没有限制。 - Ilya Gazman

显示剩余5条评论

3个回答

2

让A成为我们的数组。这是一个O(X*N)算法：

initialize set S = {0}
initialize map<int, int> parent
best_sum = inf
best_parent = -1
for a in A
     Sn = {}
     for s in S
         t = s + a
         if t > X and t < best_sum
             best_sum = t
             best_parent = s
         end if
         if t <= X
             Sn.add(t)
             parent[t] = s
         end if
     end for
     S = S unite with Sn
end for

为了打印最佳和的元素，请打印这些数字：

Subarray = {best_sum - best_parent}
t = best_parent
while t in parent.keys()
    Subarray.add(t-parent[t])
    t = parent[t]
end while
print Subarray

这个想法类似于动态规划的想法。我们计算所有可达到（可以作为子数组和获得的）小于X的和。对于数组A中的每个元素a，您可以选择参与或不参与该和。在更新步骤中，S = S unite with Sn，其中S表示a不参与的所有和，而Sn表示a参与的所有和。

您可以将S表示为布尔数组，如果该项在集合中，则设置为true。请注意，此布尔数组的长度最多为X。

总体而言，该算法的时间复杂度为O(X*N)，内存使用量为O(X)。

- sve

你是如何选择值 Y 的？同时，你能简要解释一下你在这里做什么吗？顺便说一句，我没有看到你使用了 X。 - Ilya Gazman

p是什么？我以为它和parent一样，但当我尝试打印元素时，它不起作用。然而，您的算法确实给出了正确的best_sum（通过蛮力验证）。 - Jeff Irwin

@JeffIrwin 是的，p 应该是 parent。应该没问题。我会尝试测试一下。 - sve

@svs 我觉得我的原始实现是错误的，但是你的编辑澄清了一切。我在“parent”中有一个偏移量为1的错误，现在一切都正常了。 - Jeff Irwin

1

我认为这个问题是NP-hard的，且子集和问题可以被归约为它。以下是我的归约方法：对于一个由集合S={x1,...,xn}构成的子集和实例，需要找到一个和为t的子集。假设d是两个不相等的xi和xj之间的最小距离。建立S'={x1+d/n,...,xn+d/n}并将其输入您的问题中。假设您的问题找到了一个答案；即，在S'中找到了一个子集D'，其和Y>t，且这是具有此属性的最小和。将D'的原始成员集命名为D。可能会出现三种情况： 1）Y=t+|D|*d/n，这意味着D是原始子集和问题的解。 2）Y>t+|D|*d/n，这意味着无法找到原始问题的答案集。 3）Y

- AliVar

看起来很有趣！我根据你的答案编辑了问题，以便更具体地说明我在寻找什么。请告诉我这是否改变了你的结果。 - Ilya Gazman

1

你的想法是正确的，但情况3存在问题——不清楚t是否增长得足够快。这个问题的原因在于你没有选择合适的d...即使任何非相等xi和xj之间的最小差值为d，S中任意两个不相交集合之和之间的最小非零差异可能会任意小——例如，S={1, 3, 4, 5, 6.001, 7.001}具有d=1，因此d/n=1/6，但可以产生(6.001+7.001)-(1+3+4+5)=0.002的差异。相反，选择d为S中所有数字的最大公约数... - j_random_hacker

现在，S中任意两个不相交的数集之间的差异必须是d的整数倍，这意味着情况3不可能发生 - S的任何其他子集E都不能映射到一个“潜入”到“正确”的D'（即按照情况2返回到D的那个）的S'的E'。（注意：取LCD意味着该算法仅适用于有理数，在理论上只是一种限制，因为在实践中无法在计算机上表示无理数...） - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Orhan Tuncer · Accepted Answer

正如其他答案所示，这是一个被称为“背包问题”的NP-完全问题。因此，没有多项式解决方案。但它有一个伪多项式时间算法。这解释了什么是伪多项式。该算法的可视化解释。还有一些代码。

如果这与工作相关（我已经遇到过几次，以不同的方式），我建议引入额外的限制来简化它。如果这是一个普遍的问题，您可能还想检查其他NP完全问题。其中之一列表。编辑1：

AliVar提出了一个很好的观点。给定的问题搜索Y > X，而背包问题搜索Y < X。因此，这个问题的答案需要更多的步骤。当我们试图找到Y > X的最小和时，我们也在寻找S <（Total-X）的最大和。第二部分是原始的背包问题。所以：

1.找到总计 2.解决S <（总计-X）的背包问题 3.从原始输入中减去背包解决方案中的项目列表。 4.这应该为您提供最小的Y > X