El problema de cambio de monedas

Dado un sistema monetario que consta de n monedas, cada una con un valor positivo , se pide encontrar la manera de obtener una cantidad total de x utilizando el menor número posible de monedas.

Por ejemplo, si los valores de las monedas son y necesitamos obtener 11, la mejor elección sería 1 + 5 + 5 ⇒ 3 monedas.

Entrada

La primera línea de la entrada contiene dos enteros n (1 ≤ n ≤ 100) y x (1 ≤ x ≤ ).

La siguiente línea contiene n números enteros separados por espacios (1 ≤ ≤ ).

Salida

El programa debe imprimir el número mínimo de monedas necesario para obtener x. Si no es posible formar la suma deseada x, el programa debe imprimir -1.

Ejemplos

Explicación

1. 11 → 1 + 5 + 5

2. 12 → 5 + 7

Tutorial

Observa que el enfoque greedy de tomar siempre la moneda más grande no funciona. El primer ejemplo lo demuestra claramente: si queremos obtener 11 y primero tomamos la moneda de 7 ⇒ nos queda 11-7 = 4. A continuación, necesitamos 4 monedas de 1, para un total de 5 monedas. Sin embargo, la respuesta real es 3 (5 + 5 + 1).

Mantendremos un estado d[i] que representará el número mínimo de monedas requerido para obtener la suma i. Si logramos inicializar correctamente d y actualizar todos los valores hasta la suma deseada x, la respuesta final será d[x] (el número mínimo de monedas requerido para formar x).

Inicialmente, podemos asignar a todos los valores de d infinito (significa que no se puede formar dicha suma) excepto d[0], que sí se puede obtener con 0 monedas:

c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] es 0 y d[1...x] inclusive es infinito

Después, para cada número 1...x, tratamos de encontrar la cantidad mínima de monedas necesaria para formar ese número. Si hemos llegado a un número num, probamos todas las monedas posibles para ver si podemos alcanzar num sumando el valor de la moneda a alguno de los valores previos (num - ). Si eso mejora la respuesta, actualizamos d[num]. Así, para cada num en 1...x, buscamos todos los estados previos que podrían derivar en num e intentamos mejorar el estado d[num]:

for num in range(1, x + 1):       # Iterar sobre todos los números de 1...x inclusive
    for ci in c:                  # Intentar mejorar d[num] con todas las monedas
        if num - ci >= 0:         # Si es posible obtener num con la i-ésima moneda
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])

d[num] = min(d[num], d[num - ci] + 1) es la parte clave de la solución al problema. En cada iteración, intentamos mejorar el estado de d[num] si resulta posible a través de num - . Tomamos el número mínimo de monedas requerido para obtener num - y le sumamos 1 para usar la moneda .

Cuando todos los números con todas las monedas hayan sido procesados, la respuesta quedará almacenada en d[x].

Veamos cómo se simula este algoritmo con el ejemplo: