Одна из важнейших задач в рамках разработки вендингового аппарата – это выдача сдачи наименьшим количеством монет. Сейчас выдача сдачи реализована заглушкой, которая полностью обнуляет баланс.
Мы можем с вами притянуть фактическую необходимость в выдаче сдачи монетами. Но на самом деле, эта задача нам интересна с точки зрения темы динамического программирования, которую мы попробуем рассмотреть в рамках такой интересной задачи.
Давайте четко сформулируем задачу, чтобы понять что делать. Задачу я разделю на две части, первая будет заключаться в более теоретическом поле и не будет напрямую решать задачу выдачи конкретных монет. Вторая часть, на наработках первой, будет реализовывать конкретное поведение.
Сейчас вам нужно сделать следующее:
- У вас есть набор номиналов монет (1, 5, 7, 10, 15);
- У вас есть сдача, которую нужно выдать (120);
- Вам нужно найти минимальное количество монет для выдачи сдачи;