Динамическое программирование. Задача о банкомате.

Условие

Дан банкомат, который может выдавать банкноты номиналом 1, 5, 10, 20, 50, 100 рублей. Требуется написать алгоритм, который для заданной суммы денег будет выдавать минимальное количество банкнот, необходимых для ее выдачи. Например, если задана сумма 37 рублей, то алгоритм должен выдать

• 1 банкноту номиналом 20
• 1 банкноту номиналом 10
• 1 банкноту номиналом 5
• 2 банкноты номиналом 1

Решение

Решение задачи о банкомате может быть найдено с помощью динамического программирования.

Пусть dp[i] - минимальное количество банкнот, необходимых для выдачи суммы i рублей. Тогда, для каждой суммы i от 1 до n (где n - заданная сумма), мы можем рассчитать dp[i] следующим образом:

• если i меньше минимального номинала банкноты (1 рубль), то dp[i] = infinity (невозможно выдать такую сумму);
• если i равен номиналу какой-либо банкноты, то dp[i] = 1 (можно выдать одну банкноту);
• в противном случае, мы рассматриваем все возможные номиналы банкнот и выбираем тот, который позволяет выдать сумму i с минимальным количеством банкнот: dp[i] = min(dp[i-1], dp[i-5], dp[i-10], dp[i-20], dp[i-50], dp[i-100]) + 1, где dp[i-k] - минимальное количество банкнот, необходимых для выдачи суммы i-k рублей.

Наконец, мы можем восстановить последовательность банкнот, необходимых для выдачи заданной суммы, проследовав по таблице dp от n до 0. Сложность O(n)