Алгоритм разложения суммы на неизвестные члены

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Доброго времени суток, ув.тов. программисты.

Большая просьба помочь в оптимизации алгоритма разложения суммы на составляющие члены.

Или иначе говоря — задачи выдачи сдачи, только начальные условия заранее не известны,

такие как: купюры, их кратность друг другу, разлогаемая сумма и т.д.

Дано: массив denom (купюры, могут быть от 0.001 до 99999999999999), amount (данная сумма к разложению).

Найти: ответить — разлогается ли сумма + если нет, то ближайшая разлогаемая сумма, больше заданной.

Грубо говоря — задача решена, но с учётом того, что её используют на javascript

время выполнения иногда большое очень и броузер прекращяет выполнять скрипт.

[!] Проблема в том, что когда купюры равны 10000 (к примеру!), а сумма 999999999, то итераций получается очень много и как их уменьшить я не знаю.

Суть алгоритма в том, что мы получаем массив dyn с суммами, которые мы можем разложить.

В цикле проходим по массиву, если его значени 1, то и прибавив к этому индексу любую купюру, мы тоже получим сумму.

Привер:

у нас есть 2, 3, 5 купюры, для суммы 7:

dyn [0] = 1 (т.е. сумму нуль мы можем разложить)

dyn [0+2] = 1 (а в цикле: если if (dyn [i] == 1) dyn [i+новая купюра] = 1)

dyn [2+2] = 1

dyn [4+2] = 1

dyn [6+2] = 1 (больше amount — оставляем как альтернативное решение)

dyn [0+3] = 1

dyn [2+3] = 1

dyn [3+3] = 1

dyn [5+3] = 1

dyn [0+5] = 1

dyn [2+5] = 1 (стоп!)

Подскажите пож-та, заранее благодарен.