algorithm - 查找数组中最大的整数和但不大于 x

Question

假设我们有一个整数数组：

int array = {5, 7, 4, 4, 2}
int x=10

输出将是：

10 //(4,4,2)

实现此输出的最快方法是什么？

Answer 1

您正在处理子集和问题（假设您不想要连续的子数组）。

问题是NP-Complete，并且没有已知的多项式解决方案（一般假设是不存在，但尚未证明）

但是，有一个伪多项式解决方案，使用动态规划。

Answer 2

你问的问题类似于

0-1 Knapsack problem

其中利润与重量相同。

您可以谷歌它并轻松理解算法。这可能是最快的方法。