Алгоритмы и структуры данных

Задача о размене монет

💡
Задача о размене монет — одна из самых известных задач на Динамическое Программирование. Она наглядно показывает разницу между Жадным алгоритмом и подходом Динамического Программирования, а также то, как легко ошибочно подумать, что жадного алгоритма может быть достаточно, в то время как он даёт лишь локально оптимальное, но не всегда глобально оптимальное решение.
Дан набор из n монет, каждая из которых имеет положительную стоимость . Нужно набрать сумму x, используя как можно меньше монет.
Например, если значения монет — это и мы хотим получить 11, оптимальным выбором будет 1 + 5 + 5 ⇒ 3 монеты.

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 100) и x (1 ≤ x ≤ ).
Со следующей строки считываются n чисел, разделённых пробелами: (1 ≤ ≤ ).

Выходные данные

Необходимо вывести минимальное количество монет, с помощью которых можно набрать сумму x. Если получить сумму x невозможно, надо вывести -1.

Примеры

Входные данные
Выходные данные
3 11 1 5 7
3
3 12 1 5 7
2

Пояснение

  1. 11 → 1 + 5 + 5
  1. 12 → 5 + 7
 

Учебное руководство

Обратите внимание, что жадный метод, при котором мы всегда берем максимально возможную монету, не сработает. Первый пример это хорошо иллюстрирует. Если нужно получить 11 и сначала взять 7, останется 4, а значит, придётся добирать её четырьмя монетами по 1. Итого получается 5 монет, хотя верный ответ — всего 3 (5 + 5 + 1).
Пусть у нас есть массив d, где d[i] — минимальное количество монет, необходимое для суммы i. Если правильно инициализировать d и обновить все значения до суммы x, итоговый ответ будет d[x].
Изначально можно установить все значения d равными бесконечности (сигнализируя о том, что эту сумму набрать нельзя), кроме 0 — 0 можно набрать, не используя ни одной монеты:
c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] = 0, а d[1...x] (включительно) = бесконечность
Затем для каждого числа 1...x мы пытаемся найти минимальное количество монет, необходимое для его получения. Допустим, мы рассматриваем число num. Тогда мы перебираем все доступные монеты и проверяем, сможем ли мы получить num, если добавим значение этой монеты к некоторой уже набранной сумме num - . Если это улучшает результат по количеству монет, то обновляем d[num]. То есть, для каждого num в диапазоне 1...x ищем все подходящие предыдущие состояния и пытаемся улучшить d[num]:
for num in range(1, x + 1):       # Проходимся по всем числам от 1 до x (включительно)
    for ci in c:                  # Стараемся улучшить d[num] с использованием каждой монеты
        if num - ci >= 0:         # Если можем получить num, используя i-ю монету
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])
Основная идея решения — выражение d[num] = min(d[num], d[num - ci] + 1). На каждом шаге мы пытаемся улучшить состояние d[num], используя результат для num - , и добавляем 1, расходуя монету .
Когда все числа и все монеты будут обработаны, ответом будет значение d[x].
Давайте проследим работу алгоритма на примере:
c = [1, 5, 7] и x = 11
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 (пытаемся улучшить количество монет для суммы 1)
  1. num = 2 (пытаемся улучшить количество монет для суммы 2)
  1. num = 3 (пытаемся улучшить количество монет для суммы 3)
  1. num = 4 (пытаемся улучшить количество монет для суммы 4)
  1. num = 5 (пытаемся улучшить количество монет для суммы 5)
  1. num = 6 (пытаемся улучшить количество монет для суммы 6)
  1. num = 7 (пытаемся улучшить количество монет для суммы 7)
  1. num = 8 (пытаемся улучшить количество монет для суммы 8)
  1. num = 9 (пытаемся улучшить количество монет для суммы 9)
  1. num = 10 (пытаемся улучшить количество монет для суммы 10)
  1. num = 11 (пытаемся улучшить количество монет для суммы 11)
  1. print(d[11]) ⇒ выводит 3
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue