Какой алгоритм нужен для нахождении минимальной суммы из массива, которая больше Х?
Столкнулся с проблемой на олимпиаде, так как не знаю много алгоритмов, на этой задаче попал в тупик. Значит, есть массив из положительных чисел, и есть число (Допустим, число - 28, а массив - 11, 5, 68, 9, 10, 13). Нужно найти минимальную сумму, которая больше, чем число 28 (в данном случае - 29 из 11, 13, 5). Индексация слагаемых, их колличество не важны, выводится только сумма. Как называется алгоритм для таких задач, где можно о нём почитать, и как его реализовать?
Ответы (2 шт):
Можно, например, модифицировать subset sum с помощью динамического программирования.
Сделать массив длиной сумма+минимальное число из исходного массива, в нулевой элемент записать единицу
Потом заполнить табблицу - для каждого исходного элемента v поставить единицы для тех сумм (ячеек), которые можно составить с использованием этого элемента
if (a[i-v])
a[i] = 1;
Я бы начал с перебора. Перебор на небольшом наборе отработает хорошо
void Main()
{
int[] numbers = new[] {11, 5, 68, 9, 10, 13};
int minSum = 28;
Array.Sort(numbers);
int curSum = numbers.Sum();
if(curSum < minSum) {
Console.WriteLine("Нет решений");
return;
}
Console.WriteLine(findMinSum(numbers, 0, minSum));
}
int findMinSum(int[] numbers, int index, int minsSum, int curSum = 0)
{
if (curSum > minsSum) return curSum;
if (index >= numbers.Length) return int.MaxValue;
return Math.Min(findMinSum(numbers, index+1, minsSum, curSum + numbers[index]),
findMinSum(numbers, index+1, minsSum, curSum));
}