Наименьшее кол-во купюр для размена С++

[Sauruk]

Товар стоит N рублей (N- натуральное число). Покупатель и кассир имеют неограниченное кол-во монет (купюр) различного достоинства (1,2,5,10,20,50,100,200,500,1000,50 00,10000,50000,100000 рублей). Предложить варианты расчета в которых используется минимальное кол-во монет (купюр).


Помогите с разработать алгоритм)
Оригинальный текст задания в приложении

[Biggs]

Используй Mod=% и целочисленное деление- делишь N на крупнейшую купюру , получаешь количество самых крупных купюр в N , потом остаток делишь на следующий по величине номинал и так до конца

[Sauruk]

Этим способом я лишь подсчитаю каким набором купюр можно получить N

Моя же задача найти 1 или несколько вариантов размена с использованием МИНИМАЛЬНОГО количества купюр

[rrrFer]

могу помочь за материальное вознаграждение
ICQ 395-546-218

[Biggs]

Sauruk. нет
Минимальным будет число при котором будет максимальное количество крупных купюр-так работает алгоритм

[rrrFer]

Biggs
у вас что-то работает? предлагаю сначала проверить свой алгоритм, потом советовать. Контрпример:
N = 600
купюры: 2, 200,500

очевидно, что самым оптимальным будет взять 3 купюры по 200.
по алгоритму который предлагаете вы, мы сначала берем 1 купюру номиналом 500, остается 100 => набираем 50 купюр номиналом 2.

Не надо советовать что попало

[Mad_Cat]

http://www.integr.org/olimp/3-1-1.htm

[Serge_Bliznykov]

Mad_Cat, ссылочка отличная.

Только попрошу всех заинтересовавшихся обратить внимание на один ОЧЕНЬ важный факт. В данном случае учитываются купюры УЧАСТВУЮЩИЕ в обмене с двух сторон.
на рисунке хорошо видно, что, например, для N=9000 рублей понадобится всего ДВЕ купюры: 10000 и 1000
Покупатель даёт 10000 и ему дают сдачу 1000.
записывается это 9000 = 10000 - 1000

p.s. а толковый алгоритм решения я пока не вижу...

[Biggs]

Сообщение от rrrFer

Biggs
у вас что-то работает? предлагаю сначала проверить свой алгоритм, потом советовать. Контрпример:
N = 600
купюры: 2, 200,500

очевидно, что самым оптимальным будет взять 3 купюры по 200.
по алгоритму который предлагаете вы, мы сначала берем 1 купюру номиналом 500, остается 100 => набираем 50 купюр номиналом 2.

Не надо советовать что попало

Добавьте купюру в 100 и все получится
Но ,наверное , вы правы -надо все варианты считать

[Sauruk]

Сообщение от Mad_Cat

http://www.integr.org/olimp/3-1-1.htm

Спасибо за ссылку. Попробую завтра на свежую голову адаптировать код под свою задачу