按 dec 顺序列出 n 个整数集中的 k 个对象的所有总和

Question

>我有一大组n个整数。我需要在该列表中选择 k 个元素，以便它们从大到小求和。选择的每个子集都必须对某些规则有效(规则无关紧要(。我想找到同样有效的最大求和子集。

例如，使用一小组数字(10、7、5、3、0(、3 的子集大小 3 和一个简单的规则(总和必须是素数(，代码将查看：

10, 7, 5 = 22 -> NOT PRIME, KEEP GOING
10, 7, 3 = 20 -> NOT PRIME, KEEP GOING
10, 5, 3 = 18 -> NOT PRIME, KEEP GOING
10, 7, 0 = 17 -> PRIME, STOP

我知道我可以把每个组合放在一个列表中，按降序排序，然后向下工作，直到总和通过测试，但这在空间和时间上似乎效率都非常低，特别是如果我有一组像 100 这样的大小和一个子集大小为 8。这就像我必须计算的1860亿种组合。

有没有办法在一个简单的循环中做到这一点，我从最大总和开始检查有效性，然后计算并转到下一个最大可能的总和并检查有效性等？像这样：

// Assuming set is ordered, this is the largest possible sum given the subset_size
int sum = set.Take(subset_size).Sum();
while (!IsValid(sum))
{
sum = NextLargest(set, subset_size, sum);
}
bool IsValid (int sum)
{
return sum % 2 == 0;
}
int NextLargest (int[] set, int subset_size, int current_sum)
{
// Find the next largest sum here as efficiently as possible
}

Answer 1

您不需要查看每个组合，只需查看总和较大的组合。

按降序迭代集合并检查总和。跟踪到目前为止找到的最大有效金额。当不可能获得更大的金额时，请打破循环。例如，给定子集大小 5，您找到了有效总和 53。在某些时候，您正在考虑以 10 开头的子集。由于数字是按降序排列的，因此此时您可以获得的最大总和是 50。所以这条路可以放弃。这应该会显著减少您的解决方案空间。