5.3. Ejemplos de aplicación.
Problema: Dado un conjunto de n tipos de monedas, cada una con valor ci, y dada una cantidad P, encontrar el número mínimo de monedas que tenemos que usar para obtener esa cantidad.
El algoritmo voraz es muy eficiente, pero sólo funciona en un número limitado de casos.
Utilizando programación dinámica:
- Definimos el problema en función de problemas más pequeños.
- Determinar los valores de los casos base.
- Definimos las tablas necesarias para almacenar los resultados de los subproblemas.
- Establecemos una forma de rellenar las tablas y de obtener el resultado.
5.3.1. Problema del cambio de monedas.