Los algoritmos voraces (greedy algorithms) son rutinas muy eficientes, aunque no suelen proporcionar la mejor solución a un problema. Se definen como un método expeditivo para resolver problemas complejos de forma relativamente simple. Sin saberlo, a menudo aplicamos estos principios en situaciones cotidianas, como cuando las máquinas que devuelven cambio (y también las personas) suelen aplicar un algoritmo voraz tendente a minimizar el número de monedas utilizadas.
El funcionamiento del algoritmo voraz en el cambio de monedas
Si compras algo que vale 1.30 euros y pagas con un billete de 5, es probable que te den los 3.70 de vuelta con una moneda de 2, una de 1, una de 50 cts. y una de 20, que consiste en ir eligiendo en cada paso la de mayor valor que no supera la cantidad a cubrir.
Sin embargo, en este caso, el algoritmo voraz optimiza la operación, pero podría no ser así. Si existieran monedas de 90 cts. y hubiera que devolver 1.80 euros, el algoritmo voraz elegiría una moneda de 1 euro, una de 50 cts., una de 20 y una de 10, cuando la solución óptima sería dos monedas de 90 cts.
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 que nos indique el número de monedas de S equivalente a C. En este ejemplo, 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], se incrementará t y repetiremos el mismo paso para la siguiente moneda de S.
Ejemplo práctico de limitación
Al finalizar, el algoritmo voraz nos indica que el cambio resultante para 12 con un sistema de monedas 10, 6, 5 y 1 son dos monedas de 1 y una de 10. También cabe decir que, a veces, los algoritmos voraces nos indican que no existe solución cuando realmente sí la hay.
Lea también: conceptos clave de inducción y deducción en inteligencia artificial
Programación dinámica como alternativa óptima
Cuando necesitamos garantizar la solución más eficiente, recurrimos a la programación dinámica. Este algoritmo sirve para calcular el número de monedas a retornar de una determinada suma y la cantidad de cada tipo de moneda.
En primer lugar, debemos pensar cómo plantear el problema de forma incremental. Consideramos el tipo de moneda de mayor valor, XN. Si XN > C, entonces la descartamos y pasamos a considerar monedas de menor valor. Si XN < C, tenemos dos opciones: o tomar una moneda de tipo XN y completar la cantidad restante C - XN con otras monedas, o no tomar ninguna moneda de tipo XN y completar la cantidad C con monedas de menor valor. De las dos opciones, nos quedamos con la que requiera un número menor de monedas.
Construcción de la tabla de resultados
Podemos construir una tabla para almacenar los resultados parciales que tenga una fila para cada tipo de moneda y una columna para cada cantidad posible entre 1 y C. Cada posición t[i,j] será el número mínimo de monedas necesario para dar una cantidad j utilizando sólo monedas de los tipos entre 1 e i. La solución al problema será por tanto el contenido de la casilla t[N,C].
| Método | Eficiencia | Optimalidad |
|---|---|---|
| Algoritmo Voraz | Alta (O(n), O(n²)) | No garantizada |
| Programación Dinámica | Depende del tamaño de la tabla (N x (C+1)) | Garantizada |
Siguiendo el método de la programación dinámica, se rellenará una tabla con las filas correspondientes a cada valor para las monedas y las columnas con valores desde el 1 hasta el N. Partiendo de la casilla final, el algoritmo va comprobando si su valor ha variado respecto a la casilla de la fila superior. Si no ha variado, podemos deducir que no se ha empleado ninguna moneda del tipo de la fila i; si ha variado, anotamos que se ha utilizado una moneda de ese tipo Xi y nos movemos a la casilla t[i, j-moneda[i]].
Lea también: Entiende la relación entre algoritmos y el futuro de los impuestos
Lea también: Devolución de impuestos: cálculo paso a paso
tags: #algoritmos #devolucion #de #cambio #explicacion