Запрашивает с клавиатуры номинал купюры и количество купюр и выводит экран следующее сообщение

Обновлено: 07.07.2024

мы делаем вендинговый автомат. подскажите пожалуйста по MDB протоколу.

подключаем купюроприемник
инициализируем его командой BILL TYPE
он принимает купюры в соответствии с BILL TYPE
потом даем команду POLL, купюрник шлет 06h,09h,ack и ни какого намека на тип и кол-во
принятых купюр
по команде STACKER возвращает кол-во купюр в кэш боксе.

Что не так? Как получить данные о том что он принял?

autovending » Ср июн 10, 2009 2:04 pm

Трудно по этой информации определить в чем проблема, но дам несколько
вариантов проверки.
1. Вы должны выдерживать 50 - 200 мс паузу отправки на валидатор
любой команды. Я использую тайминг 100 - 200 мс. Все опросы должны
уложиться в этот интервал.
2. Вы должны ОБЯЗАТЕЛЬНО контролировать 5 мс паузу задержки ответа валидатора на
любую коианду и ACK VMC.
3. Вы должны соблюдать процедуру инициализации Валидатора:
RESET
POLL пока не получите ответ JUST RESET (09H)
SETUP
EXPANSION IDENTIFICATION (Level 01+) (можно не выполнять)
STACKER
BILL TYPE
4. После процедуры инициализации Вы должны выполнять цикл
BILL TYPE
BILL STACKER
POLL и в завмсисмости от режима ESCROW выполнять, если нужно, укладку купюры
-----------------
В вашем случае Вы принимаете ответ о сбросе Валидатора (06H или 09H)
Естественно, Вы, надеюсь правильно формируете и контролируете байт
контрольной суммы и 9 Бит.
И еще важное замечание, Ваш VMC ОБЯЗАТЕЛЬНО должен соблюдать тайминг
опроса. В случае использования в качестве VMC PC Windows это у Вас
вероятнее всего не получится.

autovending » Ср июн 10, 2009 2:05 pm

Добрый день, Юрий.
Ваш адрес мне дал Слепичко Валерий. Если не сложно прошу помочь разобраться с
купюроприемником DBV-301-SU.
Управление от микроконтроллера, все тайминги выдерживаются по Вашим рекомендациям. 9-й
бит формирую маркем и контролирую так же. Инициализация в рекомендованном Вами порядке.
На POLL получаю 0x06 0x09.
В SETUP scalling factor равен 1000, непонятно как можно 10 р. нацело поделить на 1000.
Это правильно?
EXPANSION IDENTIFICATION (Level 01+) не использую.
STACKER считывает общее количество купюр.
Зачем 2 раза подряд давать команду BILL TYPE?
После инициализации Вы рекомендуете порядок:
BILL TYPE
BILL STACKER
POLL и в завмсисмости от режима ESCROW выполнять, если нужно, укладку купюры.
Вот это не понятно. В TYPE я всегда указываю типы 1 и 2, т.е. 10 и 50 р. Если какой-то
тип не указать, то его сразу выбросит.
STACKER опять покажет общее количество.
На все команды POLL получается неизменный ответ 0x06 0x09 без ESCROW или 0х06 0х0A c
ESCROW. Т.е. никой полезной информации. Понимаю, что что-то не так. Но что?

Непонятно как определить номинал купюры находящейся в аппарате и еще не помещенной в
stacker.

Пробую в команде BILL TYPE 0x00 0x03 0x00 0x01, т.е. маскирую для команды ESCROW 1 тип
купюр. Потом даю ESCROW 0x00. Вставляю 10 р., они фиксируются(удерживаются) в устройстве.
Если вставить 50 р. - принимаются устройством. Далее командой STACKER проверяю общее
количество купюр. При использовании комбинаций этих команд, к сожалению, не получается
добиться правильной фильтрации по номиналам.
Что делать?
Может есть типовая методика, последовательность действий, пример реализации?
Каждый производитель микроконтроллера дает различные примеры использования, так
называемые applications, appnotes и т.д. На купюрники есть что-нибудь подобное?
В общем, прошу помочь чем можете.

С уважением.
Слободчиков Александр.

autovending » Ср июн 10, 2009 2:07 pm

Определить проблему через переписку в Вашем случае мне не
представляется возможным. Надо искать самому. Дам по тексту
комментарии. См. ниже по тексту.

Юрий.
Wednesday, June 10, 2009, 9:31:07 AM, you wrote:

a> Добрый день, Юрий.
a> Ваш адрес мне дал Слепичко Валерий. Если не сложно прошу помочь
a> разобраться с купюроприемником DBV-301-SU.
Модель купюрника не имеет значения.
a> Управление от микроконтроллера, все тайминги выдерживаются по
a> Вашим рекомендациям. 9-й бит формирую маркем и контролирую так же.
a> Инициализация в рекомендованном Вами порядке.
a> На POLL получаю 0x06 0x09.
Здесь уже что-то не так. После RESET Вы действительно получите Just
RESET (09H) и сразу должны перейти на инициализационную
последовательность. В последующем цикле опросов POLL Вы должны
получать либо код 1yyyxxxxB либо ACK либо 0xxxxxxxB (но не 06h и 09h)
в случае неисправности. Если неисправностей нет Вы будете получать
только ACK либо 1yyyxxxxB.
a> В SETUP scalling factor равен 1000, непонятно как можно 10 р.
a> нацело поделить на 1000. Это правильно?
scaling factor - это стоимость наменьшей денежной единицы.
Credit = N * Scalling / Decimal, где N - цена купюры (сумма их)
a> EXPANSION IDENTIFICATION (Level 01+) не использую.
Полезная информация. Узнаете об Level MDB
a> STACKER считывает общее количество купюр.
a> Зачем 2 раза подряд давать команду BILL TYPE?
Не два раза. Первый и единственный раз при инициализации, а потом в
цикле. После нарушения тайминга инициализация повторяется.
a> После инициализации Вы рекомендуете порядок:
a> BILL TYPE
a> BILL STACKER
a> POLL и в завмсисмости от режима ESCROW выполнять, если нужно, укладку купюры.
a> Вот это не понятно. В TYPE я всегда указываю типы 1 и 2, т.е.
a> 10 и 50 р. Если какой-то тип не указать, то его сразу выбросит.
BILL TYPE нужно выполнять в цикле для того, чтобы запретить или
разрешить прием банкнот в зависимости от заполненности кешбокса или
запрета VMC.
a> STACKER опять покажет общее количество.
a> На все команды POLL получается неизменный ответ 0x06 0x09 без
a> ESCROW или 0х06 0х0A c ESCROW. Т.е. никой полезной информации.
a> Понимаю, что что-то не так. Но что?
Команду ESCROW нужно давать только в случае нахождения купюры в
кешбоксе. Ответ OAh как раз и говорит, что вы дали команду ESCROW в
момент, кода купюры в ESCROW нет.

a> Непонятно как определить номинал купюры находящейся в аппарате
a> и еще не помещенной в stacker.
Только по ответам 1yyyxxxxB на POLL

a> Пробую в команде BILL TYPE 0x00 0x03 0x00 0x01, т.е. маскирую
a> для команды ESCROW 1 тип купюр. Потом даю ESCROW 0x00. Вставляю 10
Неверно. Команда ESCROW не может идти сразу после BILL TYPE. Я
указывал ранее последовательность циклов опроса.
a> р., они фиксируются(удерживаются) в устройстве. Если вставить 50 р.
a> - принимаются устройством. Далее командой STACKER проверяю общее
a> количество купюр. При использовании комбинаций этих команд, к
a> сожалению, не получается добиться правильной фильтрации по
a> номиналам.
a> Что делать?
Следовать инструкции, указанной в предыдущем письме.
a> Может есть типовая методика, последовательность действий, пример реализации?
a> Каждый производитель микроконтроллера дает различные примеры
a> использования, так называемые applications, appnotes и т.д. На
a> купюрники есть что-нибудь подобное?
Мне неизвестны такие программы.
a> В общем, прошу помочь чем можете.

Купюры номиналом [4]= <10, 20, 50, 100>;
количество купюр[4]=;
клиент вводит сумму. условия:
1. проверить кратна ли она 10
2. сумма меньше 5 000

Показать клиенту информацию о выдаче денег. Списать деньги из массива "количество купюр".

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

то, что у меня получилось написать:

еще примечание: мы изучили только темы: объявление переменных, if, else, switch, break, continue, do while, for, массивы.

Помогите, пожалуйста, решить задачу. Совсем запуталась с ней

Последний раз редактировалось Stilet; 28.01.2013 в 20:28 . Первый совет: чтобы меньше путаться, выделяйте функции (если Вы их не проходили - советую изучить самостоятельно, это очень важная вещь, всяко важнее switch, и довольно несложная). Возьмём Ваш код и чуть преобразуем: Поскольку в действительности ограничения вида "сумма не более 5000" имеют свойство меняться, полезно вынести условие (summa%10!=0 || summa>5000) в отдельную функцию, аналогичную SumIsTooBig: Далее, стоит изменить SumIsTooBig так, чтобы она использовала состояние кассы, а не "волшебное" число 3600:
И ещё одно важное улучшение, касающееся "магических чисел": число 4 у нас "расползлось" по всей программе. Если придётся добавить пятый тип купюр, его придётся везде менять, и хоть где-нибудь, да забудем. Поэтому, перед всеми функциями, пишем: 1) continue в do <. >while(false) приводит к выходу из цикла (continue перемещает на конец итерации цикла, затем проверяется условие и. ).
2) Вы идёте от младших купюр к страшим, так что 100 выдадите как 10 десяток, а 110 выдать не сможете вовсе, причём этого даже не обнаружите.

Спасибо за помощь. Вы, наверное, потратили много времени на эту задачу!

сейчас засяду и начну вникать и "понимать", что к чему.

а 110 выдать не сможете вовсе, причём этого даже не обнаружите.

в общем виде задача не решается жадным алгоритмом, поэтому о том, что что-то там выдать нельзя лучше не вспоминать Если ТС не будет номиналы менять - то да, сойдет (они тут хитро подогнаны).

Abstraction, мне было весело читать Ваш развернутый ответ

Не могу поверить, что нам задали такую сложную задачу. Я начала изучать программирование только 3 месяца назад!

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

Я начала изучать программирование только 3 месяца назад!

Не могу поверить, что нам задали такую сложную задачу.

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

Вообще (к слову о простых и сложных программах), один тестер упоминал о такой задаче на собеседовании:

Есть программа, аргументом принимающая число N и печатающая числа от 1 до этого N. Как её можно оттестировать?

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

))))) с++ за 21 день - это не для меня! не могу выделить больше 1,5 часа в день для этого дела! и то не каждый день получается позаниматься!

может Вы будете так добры и скинете мне ссылку, где можно почитать эту книгу

Open with Desktop
View raw
Copy raw contents Copy raw contents Loading

Copy raw contents

Разбор задачи про банкомат

Задача: есть банкомат, в нем имеется ограниченное количество купюр разных номиналов. Пользователь хочет получить на руки сумму S. Если это возможно, необходимо вывести список купюр, которые дают нужную сумму, иначе надо написать, что выдача невозможна.

Например: в банкомате есть купюры: 5×1000 (5 купюр по 1000 р.), 2×500 и 4×100. Необходимо выдать сумму в 2700 р. В этом случае выдача возможна: 2×1000 + 1×500 + 2×100.

В зависимости от того, какие номиналы купюр используются, у задачи есть простое или сложное решение.

Если номиналы купюр такие, что при делении большей купюры на меньшую всегда получается целое число, то для решения задачи подходит «жадный» алгоритм. Например, если номиналы купюр равны 1000, 500 и 100 рублей, то как бы мы их не делили, получаются целые числа (1000 ÷ 500 = 2, 1000 ÷ 100 = 10, 500 ÷ 100 = 5) и этот алгоритм пригоден. Он гарантирует выдачу суммы минимальным числом купюр.

Алгоритм работает так:

пусть остаток = S

идем в цикле от самой большой купюры к самой маленькой:

берем максимально возможное количество текущей купюры так, чтобы не превысить остаток и запас купюр в банкомате
уменьшаем остаток на сумму взятых купюр

В примере выше, алгоритм будет работать так:

пусть остаток равен 2700
рассмотрим купюры в 1000 р. Максимальное количество, которое можно взять, не превышая остаток - 2 штуки. Берем 2 таких купюры и остаток уменьшается до 700 р.
рассмотрим купюры в 500 р. Берем одну и уменьшаем остаток до 200 р.
рассмотрим купюры в 100 р. Возьмем две, уменьшим остаток до нуля.
так как остаток равен нулю, выдача возможна: 2×1000 + 1×500 + 2×100

Однако этот алгоритм не работает с номиналами купюр, которые при делении не дают целых чисел. Например, в банкомате есть купюры 5×500 и 3×200 и надо выдать 600 рублей. Алгоритм, рассматривая купюры по 500, возьмет одну, остаток станет равным 100 и выдать нужную сумму не получится. В такой ситуации придется использовать более сложные алгоритмы.

Метод полного перебора

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

Например, у нас есть такой запас купюр: 3×1000, 2×500, 3×200. Мы перебираем такие комбинации:

Комбинация	Примечание
0, 0, 1	это значит 0×1000 + 0×500 + 1×200
0, 0, 2
0, 0, 3
0, 1, 0	так как комбинации 0, 0, 4 быть не может, мы обнуляем последнюю цифру и увеличиваем предыдущую
0, 1, 1
.
0, 2, 2
0, 2, 3
1, 0, 0	так как комбинаций 0, 2, 4 или 0, 3, 0 быть не может, мы переходим к 1, 0, 0
.
3, 2, 3	последняя комбинация

Общий алгоритм такой:

в начале берем комбинацию 0, 0, … 0, 1
если сумма купюр в текущей комбинации равна S, решение найдено
иначе, берем следующую комбинацию
если комбинации закончились, значит, решения нету

Алгоритм генерации комбинаций такой. Пусть у нас есть комбинация a₁, a₂ . a_n. Мы хотим получить следующую за ней комбинацию.

делаем цикл, чтобы переменная i уменьшалась от n до 1:
- увеличиваем a_i на 1
- если a_i не больше, чем запас данной купюры, выходим из цикла
- иначе обнуляем a_i и продолжаем цикл
Главный недостаток этого алгоритма — он очень медленно работает при большом количестве купюр. Допустим, у нас есть купюры 4 номиналов, каждой купюры по 1000 штук. Тогда нам придется перебрать 1000×1000×1000×1000 = 1 триллион комбинаций. Это займет очень много времени даже на современном компьютере. Как же тогда банкоматы решают эту задачу?

На помощь нам придет динамическое программирование.

Алгоритм на основе динамического программирования

Динамическое программирование — это подход, когда задачу сводят к более простым задачам. Например, чтобы определить, можно ли выдать сумму S, имея 1000 купюр, мы сначала изучаем, какие суммы можно выдать, имея 999 купюр. А для этого, в свою очередь, определяем, какие суммы можно выдать 998 купюрами, и так далее, пока не дойдем до нуля купюр. Очевидно, что имея ноль купюр, можно выдать только ноль рублей.

Для начала, выпишем все имеющиеся в банкомате купюры в виде списка, от самых больших к самым маленьким. Пусть длина этого списка равна N. Обозначим номиналы этих купюр переменными a₁ . a_N. Если у нас запас купюр составляет 3×1000, 2×500, 3×200, то список получится такой:

a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈

1000 1000 1000 500 500 200 200 200

В примере выше N = 8, a₁ = 1000, a₄ = 500.

Далее, введем функцию F(i). Эта функция определяет, какие суммы возможно выдать, имея только первые i купюр из списка. Запись F(2) = [0, 1000, 2000] обозначает, что, имея в наличии первые 2 купюры по 1000 р., мы можем выдать лишь 0, 1000 или 2000 рублей. «Выдать 0 рублей» звучит нелогично, но это нужно для работы алгоритма.

При i = 0, то есть, имея ноль купюр, мы можем «выдать» лишь 0 рублей. Нетрудно посчитать значение функции при i = 1, 2, 3:

F(2) = [0, 1000, 2000]

F(3) = [0, 1000, 2000, 3000]

Теперь попробуем определить, как найти F(i), если мы знаем F(i - 1). Например, чему равно F(4), если мы знаем F(3)? Что поменяется, если к трем купюрам в 1000 р. мы добавим купюру в 500 р.?

Получается два варианта:
- мы можем не использовать новую купюру в 500 р., и тогда мы можем выдать те же суммы, что и раньше: 0, 1000, 2000, 3000
- мы можем добавить эту купюру к любой из ранее имевшихся сумм, и получатся суммы 500, 1500, 2500, 3500
Объединяя два списка, мы получим, что F(4) = [0, 1000, 2000, 3000, 500, 1500, 2500, 3500].

Обобщая, мы можем написать: чтобы вычислить F(i), надо объединить два списка: исходный список значений F(i - 1) и список значений F(i - 1), к каждому значению которого прибавлен номинал купюры a_i.

Используя это правило, мы можем написать программу, которая последовательно рассчитывает значения функций F(0), F(1), … до F(N). На каждом шаге мы смотрим получившиеся списки сумм, и если там есть искомая сумма S, то выдача возможна. При этом, чтобы экономить память, мы можем отбрасывать все значения функции F(i), которые больше, чем S.

Оценим сложность алгоритма. Мы вычисляем значение функции от F(1) до F(N), то есть делаем N шагов. На каждом шаге мы работаем с массивом значений, в котором может быть не более S + 1 значений (суммы больше S мы отбрасываем). Получается, в процессе решения мы сделаем примерно N × S шагов. Если у нас 4 вида купюр по 1000 штук (то есть N = 4000) и суммы не превышают S = 10000, то мы сделаем 4000×10000 = 40 000 000 шагов, что гораздо лучше, чем триллион шагов, которые требует алгоритм перебора всех комбинаций.

Если вы хотите поломать голову, то можете попробовать начать писать программу. Если же идей нет, то далее я опишу готовый алгоритм.

Чтобы найти решение, мы будем вычислять значения функции F(i) при i от 0 до N, начав с набора в 0 купюр и добавляя на каждом шаге одну новую купюру. Для того, чтобы хранить список сумм, которые можно выдать на текущем шаге, заведем массив $sums . В ключе этого массива мы будем хранить сумму, а в значении - величину купюры, добавлением которой была получена эта сумма. В начале массив хранит результат F(0) и выглядит так:

Ключ Значение

0 0

Ноль слева значит, что мы можем выдать лишь сумму в 0 рублей, а 0 справа обозначает, что мы не добавляли никаких купюр. Теперь вычислим F(1). Добавим купюру a₁ в 1000 рублей. Массив примет вид:

Ключ Значение

0 0

1000 1000

Это значит, что мы можем выдать суммы в 0 и 1000 рублей. 1000 в правой колонке значит, что сумма в 1000 рублей получилась добавлением купюры a₁ (1000) к сумме 0 рублей.

Вычислим F(2), а после нее F(3), добавив купюры a₂ и a₃. Массив примет вид:

Ключ Значение

0 0

1000 1000

2000 1000

3000 1000

Теперь вычислим F(4), добавив купюру a₄ в 500 рублей. Для этого мы берем все существующие ключи из массива, добавляем к ним 500, и, если такого ключа нет, создаем его, записывая справа 500:

Ключ Значение

0 0

500 500

1000 1000

1500 500

2000 1000

2500 500

3000 1000

3500 500

Так мы делаем, пока искомая сумма S не появится в колонке слева. Если же мы сделали N шагов, использовали все купюры, а сумма S так и не появилась, то ее нельзя выдать.

Цифры в колонке слева показывают, какие суммы возможно выдать, а цифры в колонке справа позволят нам определить, какими именно купюрами это можно сделать. Например, мы хотим выдать сумму в 2500. Так как она есть в колонке «ключ», ее возможно выдать. Чтобы определить, какими купюрами она выдается, мы смотрим в правую колонку. Там стоит 500. Значит, мы берем одну купюру в 500 (остается 2000) и переходим к строчке с ключом 2000. Там справа стоит 1000, значит мы берем купюру номиналом в 1000 (остается 1000) и переходим к строке с ключом 1000. Там тоже стоит 1000, мы берем эту купюру и в остатке остается ноль. Значит, 2500 можно выдать купюрами 500 + 1000 + 1000.

Теперь вы можете написать решение задачи и сравнить его с написанным ниже.

Итак, вот алгоритм:
- пусть $s это сумма, которую надо выдать
- пусть $n это суммарное количество купюр
- преобразуем запас купюр в список $a[1 . n] , в списке купюры идут по убыванию
- создадим массив $sums и добавим в него строчку с ключом и значением 0. Это соответствует значению F(0) = [0].
- делаем цикл по $i от 1 до N:
  - // в массиве $sums мы имеем значение функции F(i - 1), и теперь по нему вычисляем F(i). Мы добавляем купюру a_i к имевшимся ранее.
  - пусть номинал добавляемой купюры $value = $a[$i]
  - создаем пустой массив $newSums . Он будет хранить новые суммы, которые получаются добавлением текущей купюры $value к старым суммам
  - обходим все ключи массива $sums . Для каждого ключа $sum :
    - вычисляем $newSum = $sum + $value
    - если $newSum > $s , пропускаем шаг цикла. Незачем тратить память на хранение больших сумм.
    - если в $sums нет ключа $newSum , то добавляем ключ $newSum в массив $newSums со значением $value
    - смотрим значение $sums[$rem] и берем купюру такого номинала
    - уменьшаем $rem на величину взятой купюры
    Мы добавляем значения в отдельный временный массив $newSums , а не напрямую в $sums , чтобы не получилось такого, что мы добавили в массив новое значение (1000 + 500 = 1500), а потом взяли его и добавили к нему ту же самую купюру еще раз (1500 + 500 = 2000).
    
    Купюры идут в списке по убыванию для того, чтобы первыми рассматривались варианты выдачи более крупными купюрами, то есть меньшим числом купюр.
    
    Задача о грабителе
    
    Задача о грабителе — это аналог задачи про банкомат и она имеет похожее решение. Грабитель проник в банк и увидел там N золотых слитков весом w₁, w₂ … w_N кг. Вес каждого слитка — целое число килограмм. В его рюкзак помещается не более K килограмм. Какие слитки он должен взять, чтобы унести максимальное количество золота?
    
    Если пытаться решить эту задачу полным перебором, то возможных комбинаций будет очень много. Допустим, у нас есть 100 слитков. Каждый слиток можно либо взять, либо не брать. Всего будет 2×2×…×2 = 2 100 ≈ 10 30 (то есть, единица с 30 нулями) вариантов выбора. Это называется "NP-сложность" - сложность решения нельзя представить многочленом.
    
    Если же использовать динамическое программирование, эта задача решается за разумное время (за N×K шагов). Попробуйте решить её, используя описанный выше подход.
    
    Задача о рюкзаке
    
    И задача про банкомат, и задача про грабителя являются частными случаями более общей задачи об укладке рюкзака. Эта задача известна математикам более 100 лет и формулируется так: есть N предметов, каждый предмет имеет вес w_i и цену p_i, и есть рюкзак вместимостью K килограмм. Какие предметы нужно положить в рюкзак, чтобы их стоимость была максимальной?
    
    Эта задача исследована. Если вес и цена предметов - целые числа, то ее можно решить методом динамического программирования. Если же вес и цена могут быть дробными, то оптимальное решение задачи неизвестно. Это значит, что нам придется перебирать все 2 N возможных комбинаций.
    
    Подробнее про динамическое программирование и задачу о рюкзаке можно прочесть тут:
    
    Рассмотрим такой алгоритм: будем выдавать банкноты наибольшего номинала, пока это возможно, затем переходим к следующему номиналу. Например, если имеются банкноты в 10, 50, 100, 500, 1000 рублей, то при N = 740 рублей такой алгоритм выдаст банкноты в 500, 100, 100, 10, 10, 10, 10 рублей. Подобные алгоритмы называют «жадными», поскольку каждый раз при принятии решения выбирается тот вариант, который кажется наилучшим в данной ситуации (чтобы использовать наименьшее число банкнот каждый раз выбирается наибольшая из возможных банкнот).
    
    Но для решения данной задачи в общем случае жадный алгоритм оказывается неприменимым. Например, если есть банкноты номиналом в 10, 60 и 100 рублей, то при N = 120 жадный алгоритм выдаст три банкноты: 100 + 10 + 10, хотя есть способ, использующий две банкноты: 60 + 60. А если номиналов банкнот только два: 60 и 100 рублей, то жадный алгоритм вообще не сможет найти решения.
    
    Но эту задачу можно решить при помощи метода динамического программирования. Пусть F(n) -- минимальное количество банкнот, которым можно заплатить сумму в n рублей. Очевидно, что F(0) = 0, F(a₁) = F(a₂) =. = F(a_k) = 1. Если некоторую сумму n невозможно выдать, будем считать, что F(n) = (бесконечность).
    
    Выведем рекуррентную формулу для F(n), считая, что значения F(0), F(1), . F(n - 1) уже вычислены. Как можно выдать сумму n? Мы можем выдать сумму n - a₁, а потом добавить одну банкноту номиналом a₁. Тогда нам понадобится F(n - a₁) + 1 банкнота. Можем выдать сумму n - a₂ и добавить одну банкноту номиналом a₂, для такого способа понадобится F(n - a₂) + 1 банкнота и т. д. Из всевозможных способов выберем наилучший, то есть:
    
    Теперь заведем массив F[n+1], который будем последовательно заполнять значениями выписанного рекуррентного соотношения. Будем предполагать, что количество номиналов банкнот хранится в переменной int k, а сами номиналы хранятся в массиве int a[k].
    
    После окончания этого алгоритма в элементе F[n] будет храниться минимальное количество банкнот, необходимых, чтобы выдать сумму n. Как теперь вывести представление суммы n при помощи F(n) банкнот? Опять рассмотрим все номиналы банкнот и значения n - a₁, n - a₂, . n - a_k. Если для какого-то i окажется, что F(n - a_i) = F(n) - 1, значит, мы можем выдать банкноту в a_i рублей и после этого свести задачу к выдаче суммы n - a_i, и так будем продолжать этот процесс, пока величина выдаваемой суммы не станет равна 0:
    
    Читайте также:

Ключ	Значение
0	0
1000	1000

Ключ	Значение
0	0
1000	1000
2000	1000
3000	1000