El problema de devolver cambio

En este problema tenemos un conjunto de monedas y hemos de seleccionar la menor cantidad de monedas para devolver un cierto valor. La optimización es precisamente obtener una selección con el menor número de monedas. Aplicaríamos un algoritmo siguiendo la misma lógica que haríamos manualmente: seleccionar una o más monedas de mayor tamaño de forma iterativa hasta que completemos todo el cambio. Vease que empezamos por las de mayor tamaño, pues si empezamos con las de menor tamaño no optimizaremos el objetivo de devolver el menor número posible de monedas.

Debemos entender la estructura básica subyacente a cualquier voraz que vimos en el tema anterior, pero no siempre será necesario escribir el código con un exceso de funciones accesorias. Por ejemplo, para plantear nuestro problema del cambio empezaremos con este código que sigue la lógica manual del párrafo anterior:

function devolverCambio1(valor=0, monedas=[]){
    //monedas = monedas.sort((a,b) => b-a));
    numIter = 1 + monedas.length;
    let cambio = monedas.map(() => 0);
    let valorCambio = 0;
    while (wxG.redondear(valorCambio, 2) < valor){
        numIter++;
        let j = 0;
        for (j=0; j<monedas.length; j++){
            numIter++;
            if (wxG.redondear(valorCambio + monedas[j], 2)<=valor) break;
        }
        cambio[j]++;
        valorCambio += monedas[j];
    }
    return cambio;
}

En el código está presente la variable numIter que no forma parte del algoritmo y que servirá para contar el número de iteraciones y de ahí obtener el coste. En un apartado siguiente veremos más sobre esto. En cuanto al resto del código observamos que están presentes las diferentes partes de la estructura de un voraz:

• El conjunto es el array monedas que contiene las clases de monedas disponibles, por ejemplo en euros 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01. Para este problema el conjunto de monedas requiere:
  1. El array debe suministrarse ordenado descendente, pues es vital para conseguir que la solución sea óptima, como veremos después. En el código verá una primera línea comentada para ordenar descendente el array en caso de que no se suministre así.
  2. Ha de tener como mínimo una clase de moneda unidad para garantizar que existe siempre una solución. Si trabajamos con euros con dos decimales, la monedad unidad será 0.01 con la que puede devolverse cualquier valor. Vease que es imposible devolver 7.31 € si no tenemos una moneda de un céntimo de euro.
  3. Hay que demostrar que la solución es óptima. El conjunto de monedas en euros cumple este principio.
  4. Suponemos en este problema que tenemos una cantidad inagotable de cada clase de monedas.
  Si se cumplen los requisitos anteriores el algoritmo voraz siempre encontrará una solución óptima. En un apartado más abajo podrá encontrar una demostración para este problema del Euro en particular.
• El resultado se compone del array cambio donde pondremos el número de monedas de cada clase que vamos a devolver siguiendo el mismo orden que el array de monedas. Para evitar tener que calcular el valor del cambio, iremos guardándolo en valorCambio.
• Sabremos si el resultado es solución cuando valorCambio === valor. Vease que no es necesario comprobar que aún quedan elementos en el conjunto puesto que disponemos de una cantidad inagotable de cada clase de monedas.
• Dentro del bucle while se agrupan las ejecuciones para seleccionar un candidato, comprobar si es completable y agregarlo al resultado.

La selección del candidato está implícita en el propio ordenamiento descendente del array de monedas. Con el bucle for siempre empezaremos seleccionando la moneda de mayor valor dado que la optimización se basa en devolver el menor número posible de monedas. Y esto sólo se consigue si vamos tomando monedas de mayor valor que no sobrepasen el valor a devolver. También podría considerarse un orden ascendente y usar el bucle con los índices al revés.

Comprobamos si es completable observando que el valor del cambio acumulado a esa moneda no sobrepasa el valor a devolver, en cuyo caso salimos del bucle y agregamos esa moneda a la solución. Lo hacemos agregando una moneda más en la posición j-ésima del cambio y actualizando valorCambio.

Si ejecutamos el ejemplo siguiente para devolver el cambio de 7.34 € usando el conjunto de monedas del euro {2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01} obtendremos el array resultado [3, 1, 0, 1, 1, 0, 2, 0]. Su valor se obtiene seleccionando las monedas 3×2 + 1×1 + 1×0.2 + 1×0.1 + 2×0.02 = 7.34

En el código anterior comprobamos en cada iteración del while si el valor acumulado es menor que el que tenemos que devolver. Tambien realizamos otra comprobación dentro del bucle for para saber si el candidato seleccionado completa la solución. En ambos casos hay que redondear el valor a dos decimales. Lo hago usando la función wxG.redondear(numero, digitos) que se explica en redondeo estándar en JavaScript.

Esto es necesario porque tenemos un problema con la precisión de los números en JavaScript. Por ejemplo, si tenemos que devolver seis céntimos de euro devolveríamos una moneda de cinco céntimos y una de un céntimo: 1 × 0.05 + 1 × 0.01 = 0.06. Pero al realizar ese cálculo JavaScript nos dará el valor 0.060000000000000005, con lo que las comprobaciones anteriores resultarán infructuosas.

Podría evitarse el redondeo si pasamos al problema el valor a devolver y el conjunto de monedas en unidades enteras, es decir, en céntimos de euro.

Mejora del algoritmo voraz para devolver cambio

Analizar el coste del algoritmo voraz nos permite hacer mejoras para reducirlo. En el tema sobre el coste de los recursivos explicábamos como ubicar un contador de iteraciones para medir el coste de un algoritmo. En el ejemplo anterior disponíamos del contador de iteraciones numIter. A la entrada del algoritmo contábamos una primera iteración más tantas como el tamaño del array de monedas, dado que hay que construir un array vacío del mismo tamaño para ubicar el cambio. Agregábamos una iteración en el inicio del bucle while y otra en el for. El ejemplo de partida que devuelve 7.34 € produce un coste de 45 iteraciones (suponiendo que se suministre en orden descendente el array de monedas).

Suponiendo que se suministre el array de monedas ordenado, el coste asintótico es O(nV) siendo n el número de monedas y V el valor a devolver. Esto es así porque en el código hay dos bucles anidados: un while y un for. El primero itera hasta alcanzar V y el segundo por el conjunto de monedas. ¿Se puede reducir ese coste?

Podemos convertir los dos bucles anidados while y for en un único bucle. Si empezamos con una moneda de 2€ y aplicamos la división entera, tenemos floor(7.34 / 2) = 3 monedas de 2€, quedando un resto de 7.34 mod 2 = 1.34, tras lo cual dividimos ese resto por la siguiente moneda de 1€ y quedarán 0.34. Seguiríamos así en este bucle hasta que el valor sea cero. Esto supone que el coste máximo será 2n+1 donde n es la longitud del array de monedas, dado que hay que rellenar un array vacío de longitud n e iterar por un bucle también de esa longitud. Para el ejemplo de cambiar 7.34€ supondrá un coste de 16 frente a los 45 del voraz anterior.

function devolverCambio2(valor=0, monedas=[]){
    //monedas = monedas.sort((a,b) => b-a));
    numIter = 1 + monedas.length;
    let cambio = monedas.map(() => 0);
    for (let j=0; j<monedas.length; j++) {
        numIter++;
        cambio[j] = Math.floor(valor / monedas[j]);
        valor = wxG.redondear(valor % monedas[j], 2);
        if (valor===0) break;
    }
    return cambio;
}

En cuanto al coste vemos en el código que hemos de crear un array para guardar el cambio que tiene una longitud de n posiciones, longitud también del bucle. Con las cabeceras de ambos bucles tenemos un coste de 2n+1. Si no suministramos el array de monedas ordenados hemos de sumar el coste de ordenar un array, que no será inferior a n log(n). Por lo tanto el coste final será de T(n) = 2n + 1 + n log(n), correspondiendo a un coste asintótico O(n log(n)) si no se suministra ordenado y O(n) en otro caso.

Demostración de la optimalidad del problema de devolver cambio

El conjunto de monedas del Euro M = { 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1, 2 } con un número inagotable de monedas de cada clase, devolverá siempre una solución óptima al aplicar el algoritmo voraz. Esto no es fácil de demostrar, pero vamos a intentarlo.

Vease que podríamos incluir los billetes de 5€, 10€, 20€, 50€, 100€, 200€, 500€ en ese conjunto de monedas, observándose que la sucesión sigue la secuencia 1, 2, 5. Para simplificar el problema realicemos los cálculos con unidades enteras. Así que si nos piden devolver 7.34 € multiplicaríamos por 100 céntimos € el valor y el conjunto de monedas y billetes, haciendo los cálculos en enteros para devolver 734 céntimos € usando el conjunto de monedas y billetes enteros en céntimos de Euro:

Podríamos definir ese conjunto de monedas y billetes en céntimos de Euro de una manera formal como sigue:

Para definirlo en Euros sólo hemos de cambiar el conjunto Q = { -2, -1, 0, 1, 2 }, pero trabajaremos con el de céntimos en la siguiente demostración. Para devolver un valor como 734 céntimos Euro dividimos entre diez sucesivamente para ir separando las unidades, decenas, centenas, etc. Así que 734 = 7 × 10² + 3 × 10¹ + 4 × 10⁰.

De forma general para devolver un valor v×10^q usaremos el subconjunto que se genera con P y ese valor concreto de q. Por ejemplo, para devolver 7 × 10² céntimos de Euro tomaremos el subconjunto de monedas { 100, 200, 500 } céntimos de Euro. Por lo tanto sólo hemos de demostrar que devolver un valor v entre 1 y 9 se realiza de una forma óptima. Como son sólo nueve valores no es díficil buscar todas las posibilidades que existen. En la siguiente tabla se relacionan todos ellos, de tal forma que por ejemplo para devolver un valor de 4 unidades tomaríamos dos monedas de 2 unidades que representamos en la tabla con la cadena de dígitos númericos "22":

Tras buscar todas las combinaciones siguiendo el principio voraz de seleccionar monedas de mayor tamaño, vemos que el algoritmo siempre selecciona en primer lugar el menor número de monedas que aparecen resaltadas en amarillo.

Si tuviéramos otro conjunto de monedas con el mismo Q y un distinto P = { 1, 3, 5, 6 } veríamos que no conseguiría devolver de forma óptima un valor v×10^q cuando v = 8, puesto que el voraz seleccionaría una moneda de 6 unidades y dos de 1 unidad (que se representa con la cadena "611" en la tabla), existiendo una selección óptima que sería una de 5 y una de 3 unidades ("53" en la tabla):

El conjunto {30, 24, 12, 6, 3, 1} era el de monedas del sistema monetario inglés antes de la normalización con valores en peniques. Este conjunto no cumple el requisito de optimalidad, puesto que si solicitamos devolver 48 el algoritmo voraz seleccionará 1×30 + 1×12 + 1×6 = 48, devolviendo tres monedas. Pero hay una solución óptima que es 2×24 = 48 con la que se devuelven sólo dos monedas.

El algoritmo voraz no encuentra un solución óptima en todos los casos con estos dos últimos conjuntos de monedas. Para resolverlo habría que utilizar una técnica diferente y más costosa: la programación dinámica que dejaremos para otro momento. Por ahora completaremos este tema realizando un demostración formal de la optimalidad del voraz para devolver cambio con un conjunto de monedas especial.

El conjunto inagotable de monedas M = { 1, p, p², p³, ..., pⁿ } con p>1 siempre encuentra una solución óptima devolviendo el menor número de monedas posibles. Podemos redefinirlo como que dado un p > 1 tenemos el conjunto M = { ∀ i ≥ 0 ⇒ ∃ m_i = pⁱ }

Sea V el valor a devolver utilizando un conjunto mínimo X que contiene la devolución de monedas de una o más clases. Aplicando el algoritmo voraz encontraría esta solución donde tenemos que 0 ≤ x_i < ∞ son las monedas a devolver de la clase m_i

Supongamos que hubiese otra solución Y que devuelva V:

Obviamente V' = V puesto que cualquier solución ha de devolver el valor V. Como X e Y son el número de monedas a devolver, tendríamos que demostrar que Y ≥ X puesto que queremos demostrar que X es el conjunto mínimo de monedas para devolver V. Esto puede expresarse así:

Si x_i = y_i para todo i entonces X = Y tratándose de la misma solución óptima. En otro caso todos serán iguales menos dos o más términos que se anulen entre ellos con objeto de cumplir V = V'.

Supongamos que todos los términos son iguales a excepción de un único j distinto, es decir x_j ≠ y_j. Este caso no sería posible pues los valores obtenidos no serían iguales dado que V-V' = (x_j - y_j) p^j ≠ 0

Supongamos que hay una pareja de términos j < k con valores absolutos de las diferencias distintos | x_j - y_j | ≠ | x_k - y_k |, uno sería positivo y otro negativo de tal forma que V-V' se anule. Tenemos entonces estas expresiones a cumplir:

En la segunda expresión anterior vemos que x_i = y_i para todo i≠j , i≠k por lo que esos términos donde x_i = y_i se anulan, por lo que demostrar que Y ≥ X se reduce a demostrar y_j + y_k ≥ x_j + x_k. En la primera expresión sacamos un factor común dividiendo por p_j recordando que j < k:

El valor de la moneda p^k-j tendría que ser de la forma siguiente:

Como p^k-j es el valor de una moneda entonces p^k-j ≥ 1 deduciéndose lo siguiente:

Queda demostrado que la solución Y contendrá las mismas o más monedas que la solución X siendo, por tanto, X una solución óptima para el caso de una pareja de términos distintos.

Si hubieran más de dos términos distintos siempre podremos reducir la demostración a un caso de una pareja de términos. Supongamos que hay tres términos j < k < s distintos en ambas soluciones:

Podríamos agrupar los dos últimos en los nuevos términos x', y':

Quedando nuevamente una demostración con una pareja de términos distintos que se resolverían como previamente hicimos. Si hay más términos distintos podemos aplicar repetidamente el proceso anterior hasta reducirlo a un caso de una pareja de términos.