У меня большой набор из 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. Это как 186 миллиардов комбинаций, которые я должен был бы вычислить.
есть способ просто сделать это в простой l oop, где я начинаю с проверки наибольшей суммы на достоверность, а затем вычисляю и go до следующей максимально возможной суммы и проверяю на действительность, et c.? Что-то вроде:
// 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
}