Algoritmos Voraces: Problema del cambio de monedas

Los algoritmos voraces (greedy algorithms en inglés) son unas rutinas muy eficientes (O(n), O(n²)) aunque no suelen proporcionar la mejor solución a un problema. Existen algoritmos voraces muy conocidos, como el Algoritmo de Dijkstra o el Algoritmo de Kruskal. Vamos a resolver mediante un algoritmo voraz el conocido Problema del cambio de monedas. El problema se presenta de la siguiente forma: Dado un sistema monetario S de longitud K y una cantidad de cambio C, devolver una solución (si existe) que nos indique el número de monedas de S equivalente a C, es decir, que nos muestre el cambio para C a partir de monedas de S. Veamos un ejemplo:

En este ejemplo nos proporcionan un sistema monetario que contiene monedas de valor 10, 6, 5 y 1. La cantidad que debemos cambiar es C=12. El algoritmo voraz siempre intentará realizar el cambio mediante monedas del mayor valor posible. Si en algún paso C es menor estricto que S[t] (t≤K), se incrementará t y repetiremos el mismo paso para la siguiente moneda de S. Al finalizar, el algoritmo voraz nos indica que el cambio resultante para 12 son dos monedas de 1 y una de 10. Cómo he comentado al principio los algoritmos voraces en muchas ocasiones no presentan la mejor solución, pues en éste ejemplo sería mejor cambiar 12 por dos monedas de 6, entendiendo por mejor solución devolver el menor número de monedas posibles.

También cabe decir que a veces los algoritmos voraces nos indican que no existe solución cuando realmente sí la hay. Un ejemplo de ello es el siguiente:

El esquema básico de un algoritmo voraz es el siguiente:

Clase EsquemaVoraz
proc voraz()
    alg
       inicializa()
       mientras (No fin())
    seleccionaYElimina()
    si (prometedor()):
       anotaEnSolucion()
    fsi
      fmientras
   fin

Para usar el esquema para resolver el Problema del cambio de moneda debemos de implementar los métodos inicializa, fin, seleccionaYElimina, prometedor y anotaEnSolucion.

• inicializa(): Crea e inicializa a ceros el array de enteros dónde se anotará la solución y pone a cero el puntero k.
• fin(): Comprueba si hemos terminado verificando que se cumpla que hemos llegado al final del recorrido del sistema monetario (es decir, que ya no hay monedas de valor más pequeño) o el cambio se haya completado (c=0).
• seleccionaYElimina(): Incrementamos el puntero k para seleccionar una moneda de menor valor.
• prometedor(): Nos indica si la moneda candidata es solución para realizar el cambio (condición: que la moneda tenga un valor inferior al cambio).
• anotaEnSolución(): Si el candidato cumple la condición lo anotamos en el array de solución.

Clase CambiodeMonedas hereda EsquemaVoraz
m: array[1..n] de Entero
c: Entero
k: Entero
sol: array[1..n] de Entero

proc inicializa()
    alg
       sol:=
       k:=0
    fin

func fin() dev (b: Lógico)
    alg
       b:=((k=n) ó (c=0))
    fin

proc seleccionaYElimina()
    alg
       k:=k+1
    fin

func prometedor() dev (b: Lógico)
    alg
       b:=(m[k] 

Más información | Greedy algorithm en Wikipedia