（在您回复另一个 SO 问题的链接或将其作为副本关闭之前，请仔细阅读该问题。这与此问题的标准变体不同，我已经搜索了很长时间，所以我很确定没有这里不是这样的问题）
我需要找出最小可能的 S是否是X[i]的某个子集的总和> = T（某个目标值，小于完整集的总和）。
该集合不是很大（大约 40 个元素），但对于指数回溯解决方案来说仍然太大。
数字和总和很大（大约 10^15），所以动态编程不起作用（可能状态的数量很大，所以记忆表很快就会耗尽内存）。
出于同样的原因，Pisinger 的线性时间算法将不起作用（它是 O(nr)，其中 r 是总和的上限，在这种情况下太大了）。
是否有一些确定性算法可以在这种大和但很少数字的情况下帮助我？我不想求助于一些近似算法。
鉴于上述条件，我相信带有分支和界限的回溯解决方案是获得确切解决方案的最佳方法。
这个想法是检查所有子集，但您可以在算法运行期间为一些可能的子集修剪计算树。
例如，假设您正在寻找S = 10^8，并且您已经找到了 的解决方案sol=10^8 + 10^7，现在，您正在检查作为 some 的超集的所有子集，X您会发现sum(X) = 10^9。无需继续检查包含 的任何子集X，您可以简单地跳过它们 - 它们不会让您达到最佳状态。
我也会尝试并行化解决方案，分支和绑定通常很容易并行化，只需要不时同步新的最佳解决方案。
As you said that the set wasn't very larget(around 40). I think the classic exponential time algorithm of complexity O(2^(n/2) n) will fit your need http://en.wikipedia.org/wiki/Subset_sum_problem#Exponential_time_algorithm.
I can briefly describe the approach here. Split the set into two equal size set, say A and B. And enumerate the subset sum for them to generate two set of size 2^(n/2), say PA and PB. Then you can sort PA and PB and use binary search to find the sum that exceeds T in time O(2^(n/2) n).