Cambio de monedas: método voraz frente a solución óptima

Introduce un conjunto de monedas y una cantidad. La página forma esa cantidad de dos maneras: con el algoritmo voraz, eligiendo cada vez la moneda de mayor valor que quepa hasta completar la cantidad o hasta que ninguna moneda sirva; y con el menor número posible de monedas, calculado al completar una tabla desde 0 hasta la cantidad. Debajo de la tabla aparecen todas las cantidades hasta el límite que elijas, con una marca en aquellas para las que el algoritmo voraz usa más monedas de las necesarias.

Ejemplo resuelto — Cambio de monedas: método voraz frente a solución óptima

Método voraz, empezando por la moneda mayor	3 monedas
Mínimo de monedas, según la tabla	2 monedas: 2×24
Monedas de más que usa aquí el método voraz	1
Importes de 1 a 240 donde falla el método voraz	42 de 240
Máximo de monedas de más entre 1 y 240	1
Primer importe donde falla el método voraz	48

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Cambio de monedas: método voraz frente a solución óptima

El problema del cambio de monedas busca el menor número de monedas que suma un importe, a partir de un conjunto de denominaciones y con una cantidad ilimitada de cada una. El algoritmo voraz toma la moneda más grande que cabe y repite el proceso. La programación dinámica resuelve el problema exactamente calculando antes todos los importes menores: M(0) = 0 y M(a) = 1 + min M(a − c) para las monedas c ≤ a. Un sistema en el que el método voraz es óptimo para cualquier importe se llama canónico.

Qué significa cada símbolo

M(a): el menor número de monedas que suma el importe a; es el número de la celda a de la tabla
G(a): el número de monedas que usa el método voraz para a
cₘ, cₘ₋₁: las monedas mayor y segunda mayor; si existe un primer importe donde falla el método voraz, es menor que su suma

Supone: Se supone que hay una cantidad ilimitada de cada moneda, que todas las denominaciones son números enteros y que el único coste es el número de monedas. Una caja que se ha quedado sin florines plantea otro problema. La cota exige una moneda de 1; sin ella, algunos importes no pueden pagarse y el método voraz puede quedarse corto incluso cuando la tabla sí encuentra una combinación.

El antiguo sistema británico vencía al método voraz en cuatro chelines 🖖

Pulsa Reino Unido pre-1971. Para pagar 48d, cuatro chelines, el método voraz toma primero la moneda más grande que cabe: una media corona (30d), seguida de un chelín (12d) y una moneda de seis peniques (6d), tres monedas en total. Dos florines de 24d suman esos mismos 48d con solo dos monedas. Desde ahí, el método voraz falla en seis importes de cada treinta peniques: 48–53d, 78–83d y así sucesivamente hasta 228–233d. Son 42 de los 240 importes de una libra. En cada caso usa exactamente una moneda de más, por eso todas las barras rojas de la franja tienen la misma altura. Esos seis importes dejan entre 18 y 23 peniques después de una o varias medias coronas; devolver una media corona y pagar 48d con dos florines ahorra una moneda. El medio penique tampoco lo arregla. Introduce las monedas en medios peniques, 1, 2, 6, 12, 24, 48, 60, y comprueba hasta 480. El primer fallo aparece en 96 medios peniques, que siguen siendo 48d; el método voraz falla en 84 de los 480 importes, los mismos 42 y el medio penique inmediatamente superior a cada uno.

Quita la media corona y el método voraz nunca falla 🖖

Pulsa Sin la media corona. Quedan las mismas monedas salvo una: 1, 3, 6, 12 y 24 peniques. La franja se queda vacía, pues el método voraz no falla en ninguno de los 240 importes. Cada moneda divide a la siguiente; en una cadena así, cualquier grupo de monedas que alcance el valor de la moneda superior puede sustituirse por esa única moneda. La media corona rompe la cadena. Treinta no es múltiplo de veinticuatro, y dos florines equivalen a una media corona más 18d, que exigen un chelín y una moneda de seis peniques; todos los fallos de la primera franja proceden de ese cambio. Añadir una moneda tampoco basta. Introduce 1, 3, 6, 12, 24, 30, 60 para recuperar la corona, cinco chelines: el recuento baja de 42 a 24, pero 48d sigue siendo el primer fallo porque una corona no sirve para ningún importe menor que ella.

Comprobar un sistema de monedas es una tarea finita 🖖

Que el método voraz falle en 48d aún no dice nada sobre 4.800d. Un teorema de Dexter Kozen y Shmuel Zaks, publicado en 1994, permite decidir un sistema para cualquier importe: si contiene una moneda de 1 y el método voraz falla alguna vez, el menor importe donde falla se encuentra estrictamente entre c₃ + 1 y c_m + c_m−1. Aquí, c₃ es la tercera moneda más pequeña, mientras que c_m y c_m−1 son las dos mayores. Pulsa Centavos de EE. UU.. Las dos monedas mayores son 100 y 50; nada falla por debajo de 150, y esa comprobación finita cubre todos los importes posibles. Para el euro llega hasta 300. La cota no puede estrecharse. Pulsa 1, 3, 4: la ventana entre 5 y 7 contiene un solo importe, 6, justo donde falla el método voraz. La línea discontinua de la franja señala la cota; cuando hay una moneda de 1, la primera barra roja siempre queda a su izquierda.

Problema resuelto al detalle

¿Qué tercera moneda puede acompañar a 1 y 5? 3 pasos
Un país tiene monedas de 1 y 5 y quiere añadir una tercera, d, comprendida entre 6 y 30. ¿Para qué valores de d será siempre óptimo el método voraz? La página prueba los sistemas de uno en uno, pero la regla de Kozen y Zaks para tres monedas permite decidir los 25 a la vez. Pulsa 1, 3, 4 para aplicar primero la regla a un sistema que la página ya ha comprobado.

Abre este problema en la herramienta
1. La regla para monedas 1 < c < d es esta: escribe d = qc + r, con 0 ≤ r < c. El sistema falla en algún importe si y solo si 0 < r < c − q. Para 1, 3, 4, tenemos d = 4 = 1 × 3 + 1; por tanto, q = 1 y r = 1, y se cumple 0 < 1 < 2. El sistema falla, y la página encuentra el primer fallo en 6:
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Ahora c = 5, así que d = 5q + r y la condición es 0 < r < 5 − q. Cuanto mayor es q, menos valores posibles quedan para r:
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. Si q = 1 (d de 6 a 9), r puede ser 1, 2 o 3, de modo que fallan d = 6, 7 y 8. Si q = 2 (de 10 a 14), r = 1 o 2: fallan 11 y 12. Si q = 3 (de 15 a 19), solo sirve r = 1: falla 16. A partir de q = 4, 5 − q vale 1 o menos y ningún r satisface la condición:
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Respuesta

Fallan seis valores: 6, 7, 8, 11, 12 y 16. Los otros diecinueve funcionan, incluidos todos los valores de d entre 17 y 30. Introduce 1, 5, 12 para observar uno de los seis casos: el método voraz paga 15 como 12 + 1 + 1 + 1, con cuatro monedas, mientras que bastan tres monedas de 5.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Ruta de aprendizaje

Por qué un algoritmo es correcto

Referencias (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.