Diferencia entre revisiones de «Algoritmia/Algoritmos voraces»

Contenido eliminado Contenido añadido
Gothmog (discusión | contribs.)
Gothmog (discusión | contribs.)
Línea 67:
===Problema del cambio de moneda===
 
* '''Enunciado''': "Se pide crear un algoritmo que permita a una máquina expendedora devolver el cambio mediante el menor número de monedas posible, considerando que el número de monedas es limitado, es decir, se tiene un número concreto de monedas de cada tipo".
Traer de http://es.wikipedia.org/wiki/Problema_de_las_monedas_mediante_el_algoritmo_voraz
 
* '''Solución''': La estrategia a seguir consiste en escoger sucesivamente las monedas de valor mayor que no superen la cantidad de cambio a devolver. El buen funcionamiento del algoritmo depende de los tipos de monedas presentes en la entrada. Así, por ejemplo, si no hay monedas de valor menor que diez, no se podrá devolver un cambio menor que diez. Además, la limitación del número de monedas también influye en la optimalidad del algoritmo, el cual devuelve buenas soluciones bajo determinados conjuntos de datos, pero no siempre. Considérense los dos siguientes ejemplos como demostración de lo dicho:
 
 
{| align="center" width="80%"
 
| align="center" width="50%" valign="top" |
 
{| border="1"
|-
|Monedas || 50 || 25 || 5 || 1
|-
| Cantidad || 3 || 4 || 1 || 6
|}
 
Si hay que devolver la cantidad 110 siguiendo el método del algoritmo voraz, se tomaría primero una moneda de 50, quedando una cantidad restante de 60. Como 50 es aún menor que 60, se tomaría otra moneda de 50. Ahora la cantidad restante es 10, por tanto ya tenemos que devolver una moneda de 5, ya que 50 y 25 son mayores que 10, y por tanto se desechan. La cantidad a devolver ahora es 5. Se tomaría otra moneda de 5, pero puesto que ya no nos queda ninguna, deberán devolverse 5 de valor 1, terminando así el problema de forma correcta.
 
| align="center" width="50%" valign="top" |
 
{| border="1"
|-
|Monedas || 6 || 4 || 1
|-
| Cantidad || 3 || 4 || 1
|}
 
Si queremos devolver la cantidad 8, siguiendo el procedimiento anterior, el algoritmo tomaría primero una moneda de 6, quedando un resto de 2. Tomaría 2 monedas de valor 1, habiendo devuelto por tanto 3 monedas, cuando es fácil ver que con 2 monedas de valor 4 se obtiene el resultado pedido.
 
|}
 
* '''Algoritmo''':
 
'''fun''' cambio (monedas_valor[1..n] '''de''' nat, monedas[1..n] '''de''' nat, importe: nat) '''dev''' cambio[1..n] '''de''' nat
m := 1;
'''mientras''' (importe > 0) '''and''' (m <= n) '''hacer'''
'''si''' (monedas_valor[m] <= importe) '''and''' (monedas[m] > 0) '''entonces'''
monedas[m] := monedas[m] – 1;
cambio[m] := cambio[m] + 1;
importe := importe – monedas_valor[m];
'''si no'''
m := m + 1;
'''fsi'''
'''fmientras'''
'''si''' importe > 0 '''entonces''' devolver “Error”; '''fsi'''
'''ffun'''
 
<small>Véase el apartado de [[../Programación dinámica|Programación dinámica]] para una solución alternativa a un problema similar.</small>
 
===Problema del maratón de películas===