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

Дан набор из 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

Пояснение

11 → 1 + 5 + 5
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

d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1 (пытаемся улучшить количество монет для суммы 1)
ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 2 (пытаемся улучшить количество монет для суммы 2)
ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 3 (пытаемся улучшить количество монет для суммы 3)
ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 4 (пытаемся улучшить количество монет для суммы 4)
ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 5 (пытаемся улучшить количество монет для суммы 5)
ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 7 ⇒ num - ci < 0
num = 6 (пытаемся улучшить количество монет для суммы 6)
ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ не обновляет
ci = 7 ⇒ num - ci < 0
num = 7 (пытаемся улучшить количество монет для суммы 7)
ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞]
ci = 5 ⇒ не обновляет
ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
num = 8 (пытаемся улучшить количество монет для суммы 8)
ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞]
ci = 5 ⇒ не обновляет
ci = 7 ⇒ не обновляет
num = 9 (пытаемся улучшить количество монет для суммы 9)
ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞]
ci = 5 ⇒ не обновляет
ci = 7 ⇒ не обновляет
num = 10 (пытаемся улучшить количество монет для суммы 10)
ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞]
ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞]
ci = 7 ⇒ не обновляет
num = 11 (пытаемся улучшить количество монет для суммы 11)
ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3]
ci = 5 ⇒ не обновляет
ci = 7 ⇒ не обновляет
print(d[11]) ⇒ выводит 3

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB