时间戳

首页 > 解决方案 > 按 DESC ORDER 列出 n 个整数集中 k 个对象的所有总和

c# - 按 DESC ORDER 列出 n 个整数集中 k 个对象的所有总和

问题描述

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

例如，使用一小组数字 (10, 7, 5, 3, 0)，子集大小为 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
}

标签： c#algorithmsortingrecursiondynamic-programming

解决方案

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

按降序遍历集合并检查总和。跟踪迄今为止发现的最大有效金额。当无法获得更大的总和时，跳出循环。例如，给定子集大小 5，您找到了一个有效的总和 53。在某些时候，您正在考虑一个以 10 开头的子集。由于数字是按降序排列的，此时您可以获得的最大总和是 50。所以这条路可以放弃。这应该会显着减少您的解决方案空间。

推荐阅读