16/12/2010, 07:25
|
| | | Fecha de Ingreso: diciembre-2010 Ubicación: Bilbao
Mensajes: 3
Antigüedad: 14 años, 3 meses Puntos: 0 | |
| Rompecabezas: cálculo de billetes
Hola.
Os propongo un pequeño rompecabezas.
Busco un algoritmo para resolver un problema que me parece un poco complicado.
Calcular, dado un número X de billetes y una cantidad Y de dinero, la combinación de billetes de 5, 10, 20, 50, 100, 200 y 500€ necesaria.
A priori es sencillo.
Por ejemplo, 80€ con 4 billetes -> 4 x 20€
105€ con 2 billetes -> 1x100€+ 1x5€
Pero claro, si subimos a dimensiones más grandes:
566 billetes = 108525 euros
pues el algoritmo típico con bucles for anidados, tarda la vida.
Tiene que haber algún algoritmo mejor, o alguna manera de resolver el problema.
¿alguien me puede dar una idea?
Gracias.
PD: Me da igual el lenguaje, es por ver un algoritmo que resuelva rápido este problema... |