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

本文介绍了子数组的总和大于给定值的最小和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

输入:由 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