子数组的总和大于给定值的最小和 [英] Smallest sum of subarray with sum greater than a given value
问题描述
输入:由 N 个正数和一个值 X 组成的数组，与 X
输出:其所有数字之和等于 Y> X 的子数组，这样就没有其他子数组的数字之和大于 X ，但小于 Y .
Input: Array of N positive numbers and a value X such that N is small compared to X
Output: Subarray with sum of all its numbers equal to Y > X, such that there is no other subarray with sum of its numbers bigger than X but smaller than Y.
这个问题有多项式解吗?如果是这样，您能提出吗?
Is there a polynomial solution to this question? If so, can you present it?
推荐答案
其他答案表明这是一个NP完全问题，称为"这解释了什么是伪多项式.
As the other answers indicate this is a NP-Complete problem which is called the "Knapsack Problem". So there is no polynomial solution. But it has a pseudo polynomial time algorithm. This explains what pseudo polynomial is.
如果这是与工作相关的(出于各种原因，我已经几次遇到此问题)，我建议引入其他限制来简化它.如果这是一个普遍的问题，您可能还需要检查其他NP-Complete问题.一个这样的列表.
If this is work related (I met this problem a few times already, in various disguises) I suggest introducing additional restrictions to simplify it. If it was a general question you may want to check other NP-Complete problems as well. One such list.
AliVar提出了一个很好的观点.给定的问题搜索Y> X，背包问题搜索Y<X.X.因此，此问题的答案还需要更多步骤.当我们试图找到Y> X的最小和时，我们也要寻找S< X的最大和.(总计-X).第二部分是原始的背包问题.所以；
AliVar made a good point. The given problem searches for Y > X and the knapsack problem searches for Y < X. So the answer for this problem needs a few more steps. When we are trying to find the minimum sum where Y > X we are also looking for the maximum sum where S < (Total - X). The second part is the original knapsack problem. So;
- 找到总数
- 为S<(总计-X)
- 从原始输入中跟踪背包解决方案中的项目列表.
- 这应该给您最小的Y> X
这篇关于子数组的总和大于给定值的最小和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
