Дистанционная подготовка: Из множества чисел получить определенную сумму
Из множества чисел получить определенную сумму
от Иван Волков - Среда 5 Июль 2017, 16:10
  Здравствуйте.
Возник вопрос: существует ли алгоритм, который позволяет эффективно определить, можно ли из ограниченного множества чисел получить определенную сумму, если данные числа разрешается использовать неограниченное кол-во раз.
Для наглядности приведу примеры:

Имеются числа: 3 7 11
Нужно проверить, можно ли их просуммировать так, чтобы получилось число 17.
Ответ: да. (7 + 7 + 3)

Имеются числа: 2 4 6
Нужно проверить, можно ли их просуммировать так, чтобы получилось число 3.
Ответ: нет.

Единственное решение, которое мне пришло в голову - перебор. Но с большими числами (> 10^8) такой метод не может быть использован.

Интересует, сталкивался ли кто-нибудь с такой проблемой и какое решение было найдено.
Re: Из множества чисел получить определенную сумму
от Peter Cherepanov - Среда 5 Июль 2017, 21:52
  Посмотрите, как такие задачи решаются методом динамического программирования.