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

[CVA]

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

Большая просьба помочь в оптимизации алгоритма разложения суммы на составляющие члены.
Или иначе говоря - задачи выдачи сдачи, только начальные условия заранее не известны,
такие как: купюры, их кратность друг другу, разлогаемая сумма и т.д.

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

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

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


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

Привер:

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

dyn[0] = 1 (т.е. сумму нуль мы можем разложить)
dyn[0+2] = 1 (а в цикле: если if (dyn == 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 (стоп!)



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

[airyashov]

Вы именно используете массив, размер которого получается всегда более или равен раскладываемой сумме?

[CVA]

Более, т.к. если 7 нельзя получить, тогда ближайшее большее (т.е. 8)

[airyashov]

Я прочитал ответы на ваш вопрос на др форумах добавить нечего

[CVA]

Благодарю за участие

[chur]

День добрый.

Предлагаю такой вариант для "большого" amount (большого, по сравнению с номиналом купюр).

Для каждой пары купюр определяем, скажем так, конечный остаток больше нуля. Что имею ввиду, проще показать на примере.
Даны купюры: 9, 12, 17
1-ая пара: 9 и 12. Остаток от деления 12/9 -> 3. Остаток от деления 12/3 -> 0, 9/3 -> 0. Т.о. для этой пары -> 3.
2-ая пара: 9 и 17. Остаток от деления 17/9 -> 8. Остаток от деления 17/8 -> 1, 9/8 -> 1. Для этой пары -> 1.
3-ая пара: 12 и 17. Остаток от деления 17/12 -> 5. Остаток от деления 17/5 -> 2, 12/5 -> 2. Остаток от деления 17/2 -> 1, 12/2 -> 0, 5/2 -> 1. Для этой пары тоже -> 1.

В принципе, когда нашли первую 1 (единицу), данный этап можно заканчивать. Мы имеем две купюры которыми можно разложить любой "большой" amount. В нашем случаем 9 и 17.

Далее решаем в целых числах уравнение: 9m + 1 = 17n. Другими слова, мы определяем какое количество купюр с меньшим номиналом необходимо поменять на ккакое количество купюр большего номинала чтобы сумма увеличилась на 1. В нашем случаем m=15, n=8.

И последний этап. Представляем amount ввиде 9a + b. И, собственно ответ: купюр номиналом 9 - a-(b*m) штук, купюр номиналом 17 - b*n штук.

Надеюсь, объяснил идею внятно. Естественно, простор для оптимизации есть . Хотел бы отметить, что если конечный остаток больше единицы, то с данным набором номиналов можно разложить amount только кратный конечному остатку.

[CVA]

не катит: пример 430 на 100 50 20 = 100 100 100 50 20 20 20 20

[chur]

не понял, что не катит: 20 х 19 + 50 х 1.
Или в условии мелким почерком задано найти минимальное количество купюр?

[CVA]

кому интересно продолжение здесь:
http://www.developers.org.ua/forum/topi ... post-13253

[atavin-ta]

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