给定一组正整数，我想要那些整数的子集，其总和是超过阈值的最小总和。
问问题
948 次
3 回答
4
您的问题是子集和问题的变体，并且是 NP 完全的。
要了解原因，让我们假设您有一个可以解决您的问题的算法，并且它会产生一个带有 sum 的答案。然后你已经证明不存在等于 s - 1 的整数子集，即你有一个子集和问题的解决方案。
如果性能不是问题，您不妨列举所有可能的集合。如果性能是一个问题，您可以尝试在 Wikipedia 页面上查找有关如何优化此类算法的想法，例如使用动态编程。该页面上的算法实际上应该与子集和问题一样有效地解决您的问题。
于 2010-02-25T22:17:27.823 回答
0
“最小和”：有一个经典的“最大和”问题，在这里描述得很好：http ://wordaligned.org/articles/the-maximum-subsequence-problem
这只是一个“超过阈值”条件的微小变化——只是循环中的一个额外的 IF 语句。
于 2010-02-25T22:20:22.273 回答
0
我有同样的问题！如果所有 N 个整数都是正数并且以常数 C 为界，则存在一个解，时间和空间要求为 O(NC)。
Pisinger 发现了一种线性时间动态规划算法，可以找到阈值下的最大值，这就像你的问题的逆。所以，如果你从整数的总和中减去你想要的阈值，你可以使用这个新的阈值和 Pisinger 的算法来找到所有不在想要的集合中的数字。
根据所讨论的整数的大小，这可能可行，也可能不可行。
于 2013-06-20T20:22:31.560 回答