Как собрать пазл из чисел? Дано несколько чисел [1, беск). Дано ключевое число N [1, беск).
Задача заключается в том, что бы подобрать числа (в колве от 1 до 10) из множества таким образом, что бы их сумма была максимально приближена к заданному N, но не больше N.
Например, при множестве 1, 9, 3, 5, 999 и N = 4, решением будет 1, 3
Возможно есть готовые алгоритмы решения подобного? Пока в голову приходит тупой перебор с отсеиванием чисел > N.

Предыдущий
вопрос Следующий
вопрос

Да, существует алгоритм решения данной задачи, который называется "Динамическое программирование".

Для решения этой задачи можно воспользоваться следующим подходом:

Создать массив dp размером N + 1, где каждый элемент dp[i] будет хранить максимальную сумму чисел, которая не превышает i.Инициализировать dp[0] = 0.Для каждого числа num из заданного множества, пройтись по массиву dp от N до num и обновить значения dp[j] = max(dp[j], dp[j - num] + num).После завершения всех итераций в массиве dp, нужно восстановить искомое подмножество чисел. Для этого можно начать с dp[N] и восстановить значения чисел, учитывая, было ли данное число взято в сумму или нет.

Таким образом, алгоритм находит оптимальное подмножество чисел, сумма которых максимально приближена к заданному числу N.

Если у вас возникнут дополнительные вопросы или понадобится помощь с реализацией данного алгоритма, пожалуйста, не стесняйтесь задавать их.