Программирование на Python. Ведьмаку заплатите чеканной монетой

Всем известно, что ведьмак одолеть любых чудовищ, однако его услуги обойдутся недешево, к тому же ведьмак не принимает купюры, он принимает только чеканные монеты. В мире ведьмака существуют монеты с номиналами 1, \, 5, \, 10, \, 251,5,10,25.

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

Формат входных данных 
На вход программе подается одно натуральное число, цена за услугу ведьмака.

Формат выходных данных
Программа должна вывести минимально возможное количество чеканных монет для оплаты.

​

sm = int(input())

coins = [1, 5, 10, 25]

ls = [0] * (sm+1)

for i in range(1, sm+1):

   ls[i] = float('inf')

   for coin in coins:

       if coin <= i:

           ls[i] = min(ls[i], ls[i-coin]+1)

print(ls[-1])

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

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

Давайте решим эту задачу на примере.

1) Пользователь вводит цену за услугу ведьмака, допустим, она равна 98.

2) Создадим переменную "счетчик_монет" и установим ее равной 0. Эта переменная будет содержать количество использованных монет.

3) Программа проверяет, какую монету можно вычесть из текущей суммы.
- 98 >= 25 - мы можем вычесть 25.
- Обновляем значение счетчика монет: счетчик_монет = 1.
- Обновляем значение суммы: 98 - 25 = 73.
- Продолжим выполнение цикла.

4) Теперь сумма равна 73. Снова проверяем, какую монету можно вычесть.
- 73 >= 25 - мы можем вычесть 25.
- Обновляем значение счетчика монет: счетчик_монет = 2.
- Обновляем значение суммы: 73 - 25 = 48.
- Продолжим выполнение цикла.

5) Теперь сумма равна 48. Снова проверяем, какую монету можно вычесть.
- 48 >= 25 - мы можем вычесть 25.
- Обновляем значение счетчика монет: счетчик_монет = 3.
- Обновляем значение суммы: 48 - 25 = 23.
- Продолжим выполнение цикла.

6) Теперь сумма равна 23. Снова проверяем, какую монету можно вычесть.
- 23 >= 10 - мы можем вычесть 10.
- Обновляем значение счетчика монет: счетчик_монет = 4.
- Обновляем значение суммы: 23 - 10 = 13.
- Продолжим выполнение цикла.

7) Теперь сумма равна 13. Снова проверяем, какую монету можно вычесть.
- 13 >= 10 - мы можем вычесть 10.
- Обновляем значение счетчика монет: счетчик_монет = 5.
- Обновляем значение суммы: 13 - 10 = 3.
- Продолжим выполнение цикла.

8) Теперь сумма равна 3. Снова проверяем, какую монету можно вычесть.
- 3 >= 1 - мы можем вычесть 1.
- Обновляем значение счетчика монет: счетчик_монет = 6.
- Обновляем значение суммы: 3 - 1 = 2.
- Продолжим выполнение цикла.

9) Теперь сумма равна 2. Снова проверяем, какую монету можно вычесть.
- 2 >= 1 - мы можем вычесть 1.
- Обновляем значение счетчика монет: счетчик_монет = 7.
- Обновляем значение суммы: 2 - 1 = 1.
- Продолжим выполнение цикла.

10) Теперь сумма равна 1. Снова проверяем, какую монету можно вычесть.
- 1 >= 1 - мы можем вычесть 1.
- Обновляем значение счетчика монет: счетчик_монет = 8.
- Обновляем значение суммы: 1 - 1 = 0.
- Продолжим выполнение цикла.

11) Сумма равна нулю, поэтому мы выходим из цикла.

12) Выводим значение счетчика монет: счетчик_монет = 8. Это и будет минимально возможным количеством чеканных монет для оплаты услуги ведьмака.

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