Problema del cambio de monedas
Lección 8 de 15 del curso Programación Dinámica 101 de Coddy.
El problema del cambio de monedas es un problema clásico de programación dinámica. Dado un conjunto de monedas con diferentes denominaciones y una cantidad total de dinero, la tarea consiste en encontrar el número mínimo de monedas necesarias para completar la cantidad dada.
Por ejemplo, supongamos que tenemos monedas con denominaciones [1, 5, 10] y queremos completar la cantidad 15. El número mínimo de monedas necesarias sería 2 (una moneda de 10 y una moneda de 5).
Para resolver este problema utilizando programación dinámica, podemos crear una tabla con filas que representen las denominaciones de las monedas y columnas que representen las cantidades desde 0 hasta la cantidad total dada. Luego, completamos la tabla de abajo hacia arriba calculando el número mínimo de monedas necesarias para completar cada cantidad utilizando las monedas de cada denominación.
Desafío
IntermedioEscribe un programa que reciba dos entradas: una lista de denominaciones de monedas y una cantidad objetivo, y devuelva el número mínimo de monedas necesarias para alcanzar la cantidad objetivo.
Por ejemplo, para las denominaciones [1, 5, 10] y la cantidad objetivo 15, el resultado debería ser 2.
Pruébalo tú mismo
def min_coins(coins, target):
# Escribe el código aquíTodas las lecciones de Programación Dinámica 101
3Algoritmos de programación dinámica
Subsecuencia común más largaProblema de la mochilaProblema del cambio de monedasDistancia de edición