Algoritmos Codiciosos

Monedas de Estados Unidos

Al hacer cambios, lo más probable es que desee minimizar la cantidad de monedas que está dispensando para cada cliente, para que no se agote (¡ o moleste al cliente!). Afortunadamente, la informática ha brindado a los cajeros de todas partes formas de minimizar el número de monedas adeudadas: algoritmos codiciosos.

Según el Instituto Nacional de Estándares y Tecnología (NIST), un algoritmo codicioso es aquel "que siempre toma la mejor solución inmediata o local al encontrar una respuesta. Los algoritmos codiciosos encuentran la solución óptima general o global para algunos problemas de optimización, pero pueden encontrar soluciones menos que óptimas para algunos casos de otros problemas.”

¿Qué significa todo eso? Bueno, supongamos que un cajero le debe a un cliente algún cambio y en el cajón de ese cajero hay cuartos (25¢), monedas de diez centavos (10¢), monedas de cinco centavos (5¢) y centavos (1¢). El problema a resolver es decidir qué monedas y cuántas de cada una entregar al cliente. Piense en un cajero" codicioso " como uno que quiere sacar el mayor provecho posible de este problema con cada moneda que saca del cajón. Por ejemplo, si a algún cliente se le deben 41¢, el primer bocado más grande (es decir, el mejor bocado inmediato o local) que se puede tomar es de 25¢. (Ese bocado es "mejor" en la medida en que nos acerca a 0¢ más rápido que cualquier otra moneda.) Tenga en cuenta que un bocado de este tamaño reduciría lo que era un problema de 41¢ a un problema de 16¢, ya que 41 - 25 = 16. Es decir, el resto es un problema similar pero más pequeño. No hace falta decir que otro bocado de 25¢ sería demasiado grande (suponiendo que el cajero prefiera no perder dinero), por lo que nuestro cajero codicioso pasaría a un bocado de tamaño 10¢, dejándolo con un problema de 6¢. En ese momento, la codicia exige un bocado de 5¢ seguido de un bocado de 1¢, momento en el que se resuelve el problema. El cliente recibe un cuarto, una moneda de diez centavos, un níquel y un centavo: cuatro monedas en total.

Resulta que este enfoque codicioso (es decir, el algoritmo) no solo es óptimo a nivel local, sino también a nivel mundial para la moneda de Estados Unidos (y también la de la Unión Europea). Es decir, siempre que un cajero tenga suficiente de cada moneda, este enfoque de mayor a menor producirá la menor cantidad de monedas posible. ¿Qué tan pocos? ¡Bueno, dínoslo tú!