输入：n个正数和一个值x的数组，使得n比x小
输出：子阵的所有数之和等于y>x，这样就没有其他子阵的数之和大于x但小于y。
这个问题有多项式解吗？如果有的话，你能介绍一下吗？
最佳答案
如其他答案所示，这是一个np完全问题，称为“Knapsack Problem”。所以没有多项式解。但它有一个伪多项式时间算法。This explains what pseudo polynomial is。
A visual explanation of the algorithm。
And some code。
如果这是与工作相关的（我已经多次遇到这个问题，伪装成各种形式），我建议引入额外的限制来简化它。如果这是一个一般性问题，你可能也要检查其他np完全问题。One such list.
编辑1：
阿利瓦尔说得很好。给定的问题搜索y>x，背包问题搜索y找出总数
求解s将背包解决方案中的项目列表从原始输入分包。
这应该给你最小的y>x