subset-sum - 总和是超过特定阈值的最小总和的子集

Question

给定一组正整数，我想要这些整数的子集，其总和是超过阈值的最小总和。

Answer 1

您的问题是 Subset Sum Problem 的变体并且是 NP 完全的。

为了了解原因，我们假设您有一个可以解决您的问题的算法，并且它生成的答案为 sum 。那么你已经证明不存在等于 s - 1 的整数子集，即你有子集和问题的解。

如果性能不是问题，您不妨枚举所有可能的集合。如果性能是一个问题，您可以尝试在维基百科页面上查找有关如何优化此类算法的想法，例如通过使用动态编程。该页面上的算法实际上应该几乎与子集求和问题一样有效地解决您的问题。