和大于给定值的子数组的最小和

Question

输入：N个正数数组和一个值X使得N 比 X
小输出：其所有数之和等于Y > X的子数组，因此没有其他子数组其数之和大于X 但小于 Y.

这道题有多项式解吗？如果有，可以介绍一下吗？

Answer 1

让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)。

Answer 2

我认为这个问题是NP难的，子集和可以归约到它。这是我的减少：对于具有集合 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 < t + |D|*d/n。在这种情况下，分配 t=Y 并重复该问题。由于新 t 的值增加了，这种情况不会呈指数重复。因此，该过程在多项式时间内终止。

Answer 3

正如其他答案所表明的那样，这是一个 NP 完全问题，称为“Knapsack Problem". So there is no polynomial solution. But it has a pseudo polynomial time algorithm. This explains what pseudo polynomial is。

A visual explanation of the algorithm.

And some code.

如果这是与工作相关的（我已经多次遇到过这个问题，以各种形式出现）我建议引入额外的限制来简化它。如果这是一个一般性问题，您可能还想检查其他 NP-Complete 问题。 One such list.

编辑 1：

AliVar 说得很好。给定问题搜索 Y > X，而背包问题搜索 Y < X。因此，此问题的答案需要更多步骤。当我们试图找到 Y > X 的最小总和时，我们也在寻找 S <（总计 - X）的最大总和。第二部分是原始背包问题。所以;

求总数
解决 S <（总计 - X）的背包问题
从原始输入中减去背包解决方案中的项目列表。
这应该给你最小的 Y > X

和大于给定值的子数组的最小和

Smallest sum of subarray with sum greater than a given value

arrays

algorithm

performance

numbers