Contando monedas

En mi entrevista con Amazon (sobre la que escribí aquí, aquí, aquí y aquí) uno de los ingenieros me hizo la siguiente pregunta relacionada con optimización combinatoria basada en el conocido problema de la mochila, también llamado KP: dado un precio arbitrario y una lista de monedas de distinto valor, diseña un algoritmo que sea capaz de encontrar la combinación que resulte en el menor número de monedas utilizadas. Al principio, me pareció obvio que, utilizando el mayor número posible de la moneda más grande, después de la siguiente más grande, etc., conseguiríamos el número mínimo de monedas utilizadas. Por ejemplo, para acabar con un valor de $1.09, teniendo disponibles monedas de la lista [$0.01, $0.07, $0.10, $0.25], utilizaríamos la siguiente distribución de monedas:

Valor de la moneda	$0.25	$0.10	$0.07	$0.01
Número de monedas	4	0	1	2

Así, primero utilizamos tantas monedas de $0.25 como podamos. Si utilizamos 5, tendríamos un valor total de $1.25, por lo que ya nos habríamos pasado. De acuerdo al algoritmo antes descrito, utilizaremos sólo 4 para un valor total de $1.00. Entonces, pasamos a la siguiente moneda más grande, con valor de $0.10. Si utilizamos 1 moneda de $0.10, tendremos un valor total de $1.10 y nos habremos pasado otra vez, por lo que no habrá que utilizar ninguna moneda de ese valor. Aplicando las mismas reglas a todas las monedas en orden decreciente, acabaríamos con la distribución representada en la anterior tabla. Utilizamos un total de 7 monedas y, salvo que esté equivocado en algo muy obvio, no hay ninguna manera más óptima de distribuir las monedas para utilizar un número menor de ellas. ¡Pero mi algoritmo era erróneo! Después de pelearme con la implementación del código, mi entrevistador utilizó la prueba por contradicción para demostrar que mi algoritmo no siempre encontraría la solución más óptima. ¿Qué pasaría si el valor buscado fuese $1.15 utilizando la misma lista de monedas? Con el algoritmo de antes, tendríamos la siguiente distribución:

Valor de la moneda	$0.25	$0.10	$0.07	$0.01
Número de monedas	4	1	0	5

Estaríamos utilizando un total de 10 monedas, pero obviamente la siguiente distribución es más óptima:

Valor de la moneda	$0.25	$0.10	$0.07	$0.01
Número de monedas	4	0	2	1

Puesto que con la última distribución sólo utilizamos 7 monedas, queda demostrado que el algoritmo ha fallado. Es importante mencionar que, si tuviéramos una moneda de $0.05 en vez de $0.07, el algoritmo funcionaría perfectamente, la explicación está relacionada con la primalidad de los números de la lista entre ellos. Con mi algoritmo y mi autoestima hechos trizas, mi entrevistador me preguntó si había algún otro algoritmo que pudiese encontrar la solución más óptima, y en ese momento le respondí que posiblemente no haya nada mucho mejor que utilizar una búsqueda de fuerza bruta. Entonces, me dí cuenta de que el problema podía ser representado como una serie de restricciones lineares por lo que podía ser resuelto mediante la programación lineal. Después de que mi entrevistador le pidiera 5 minutos más a su relevo, que ya estaba esperando en la puerta, me permitió que le explicara como resolvería el problema si tuviese acceso a algún método para resolver ecuaciones lineales, como el algoritmo simplex. Tras haber estudiado con detalle el problema de la mochila en la universidad con anterioridad, estaba bastante decepcionado por haber sido incapaz de reconocer una solución que no estuviese errada sin la ayuda del entrevistador.