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

Question

输入:N 正数和一个值X 使得N 小于<强>X
输出:其所有数字之和等于Y > X的子数组，使得没有其他子数组其数字之和大于X> 但小于 Y。

这道题有多项式解吗？如果是这样，你能介绍一下吗？

Answer 1

正如其他答案所表明的那样，这是一个 NP 完全问题，称为“Knapsack Problem”。所以没有多项式解。但是它有一个伪多项式时间算法。 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)的最大总和。第二部分是原始背包问题。所以;

1. 求总数
2. 为 S < (Total - X) 解决背包问题
3. 从原始输入中减去背包解决方案中的项目列表。
4. 这应该给你最小的 Y > X