Algoritmos y Estructuras de Datos

El problema de cambio de monedas

💡
El problema de cambio de monedas (coin change) es uno de los más populares dentro de la Programación Dinámica. Ilustra vivamente la diferencia entre los enfoques Greedy y la Programación Dinámica, y cómo se puede caer en la trampa de pensar que la solución greedy puede ser suficiente, cuando en realidad solo produce una respuesta subóptima en lugar de resolver el problema de manera global.
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

Entrada
Salida
3 11 1 5 7
3
3 12 1 5 7
2

Explicación

  1. 11 → 1 + 5 + 5
  1. 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 - c_i). 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 - c_i. Tomamos el número mínimo de monedas requerido para obtener num - c_i y le sumamos 1 para usar la moneda c_i.
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:
c = [1, 5, 7] y x = 11
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 (intentar mejorar la cantidad de monedas para obtener la suma de 1) ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 2 (intentar mejorar la cantidad de monedas para obtener la suma de 2) ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 3 (intentar mejorar la cantidad de monedas para obtener la suma de 3) ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 4 (intentar mejorar la cantidad de monedas para obtener la suma de 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
  1. num = 5 (intentar mejorar la cantidad de monedas para obtener la suma de 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
  1. num = 6 (intentar mejorar la cantidad de monedas para obtener la suma de 6) ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ no se actualiza ci = 7 ⇒ num - ci < 0
  1. num = 7 (intentar mejorar la cantidad de monedas para obtener la suma de 7) ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞] ci = 5 ⇒ no se actualiza ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
  1. num = 8 (intentar mejorar la cantidad de monedas para obtener la suma de 8) ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞] ci = 5 ⇒ no se actualiza ci = 7 ⇒ no se actualiza
  1. num = 9 (intentar mejorar la cantidad de monedas para obtener la suma de 9) ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ no se actualiza ci = 7 ⇒ no se actualiza
  1. num = 10 (intentar mejorar la cantidad de monedas para obtener la suma de 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 ⇒ no se actualiza
  1. num = 11 (intentar mejorar la cantidad de monedas para obtener la suma de 11) ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3] ci = 5 ⇒ no se actualiza ci = 7 ⇒ no se actualiza
  1. print(d[11]) ⇒ imprime 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