假设我们有一个整数数组:
int array = {5, 7, 4, 4, 2}
int x=10
输出将是:
10 //(4,4,2)
实现此输出的最快方法是什么？
最佳答案
您正在处理一个 Subset Sum Problem (假设您不想要连续的子数组)。
问题是NP-Complete ，并且没有已知的多项式解(一般假设不存在，但是it is not proven yet)
然而，有一个pseudo polynomial solution, using Dynamic Programming .
关于algorithm - 查找数组中最大的整数和但不大于 x，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13209278/