Это решение предполагает, что числа n1, n2, ... nN являются целыми числами (или что они имеют "наименьший общий делитель")
У меня есть алгоритм O (K * N) (спасибо, что отсутствует за исправление). Идея - немного динамического программирования, немного Сита Эратосфена.
Начните с создания списка L из K + 1 логических значений. L[i]
верно, если вы можете «построить» число i (подробнее об этом позже). Все значения L инициализируются как false
, кроме L[0]==true
Начните с первого номера n1. Для каждого значения i от 1 до K проверьте, если L[i-n1]==true
. Конечно, если i-n1<0
, то поступайте так, как если бы L[i-n1]==false
. Если L[i-n1]==true
, тогда измените L[i]
на true
. Теперь у вас есть L[n1]==true
, L[2*n1]==true
, L[3*n1]==true
...
Что теперь означает L? L представляет числа в [0..K], которые могут быть построены только с n1. Если L[K]==true
, поздравляю, есть решение, построенное только с n1!
Возьмите число n2 и сделайте то же самое. Для каждого значения i от 1 до K, такого, что L[i]==false
, проверьте, если L[i-n2]==true
. Если это так, измените L[i]
на true
.
Что теперь означает L? L представляет числа в [0..K], которые могут быть построены с n1 и n2. Если L[K]==true
, поздравляю, есть решение, построенное только с n1 и n2!
Если после заполнения L всеми значениями N L[K]==false
, ваша проблема не решена.
Проблема с динамическим программированием заключается в том, что всегда сложно найти решение, когда вы доказали, что он существует ... Вам нужен еще один список S, такой, что S[i]
описывает, какие коэффициенты необходимы для "построения" я. (существует только если L[i]==true
конечно)