Problema con cajero automático

[tete69]

Hola a todos!
Me ha surgido un problema con un código y no le encuentro solución posible...

El objetivo es crear un cajero automático que entregue una cantidad determinada con el mínimo número de billetes posible. El algoritmo, que parece sencillo en un principio, se complica cuando cambiamos la disponibilidad de ciertos billetes:

Código PHP:

  <?
 
$x=0;
 
$n=$_POST['cantidad'];
 
if($_POST['500']==true){$x=$x+1;$moneda[$x]='B500';$valor[$x]=500;}
 
if($_POST['200']==true){$x=$x+1;$moneda[$x]='B200';$valor[$x]=200;}
 
if($_POST['100']==true){$x=$x+1;$moneda[$x]='B100';$valor[$x]=100;}
 
if($_POST['50']==true){$x=$x+1;$moneda[$x]='B50';$valor[$x]=50;}
 
if($_POST['20']==true){$x=$x+1;$moneda[$x]='B20';$valor[$x]=20;}
 
if($_POST['10']==true){$x=$x+1;$moneda[$x]='B10';$valor[$x]=10;}
 
for ($p=1;$p<=$x;$p=$p+1)
 
 {while ($valor[$p]<=$n)
 
     {$cambio[$p]=$cambio[$p]+1;
 
       $n=$n-$valor[$p];
 
     }
 
 }
 
for ($p=1;$p<=$x;$p=$p+1) {print $moneda[$p] ; print ":"; print $cambio[$p];print "---";}
 
?>   

Dónde n es la cantidad a entregar. El fallo aparece en muchos casos, por ejemplo:

billetes disponibles{200,50,20}
n=210
Y otros similares...

Creo que la solución es recursiva, pero voy bastante mal y agradeceria que si alguien da con una solución me pudiera guiar un poco.

Gracias por vuestra atención y tiempo ;)

[cuasatar]

Por el ejercicio que realizas supongo que se tratara de un trabajo de la universidad. No se si existen limitaciones a la hora de entregar los billetes o no, pero lo primero que estaria por mejorar es averiguar si en verdad existen los billetes. Un cajero de verdad no tiene infinita cantidad de billetes y se deberian descontar cada vez que un usuario hace uso de ellos.

Si el ejercicio no impone ese problema podemos verlo desde otra perspectiva, es una sugerencia que se me ocurre:

Si por decir algo la cantidad a entregar son 320 euros se deberia hacer un recorrido del valor del mayor billete al menor e ir dividiendo. Si el valor de la división de la parte entera es 0 lo que sea significa que no se puede entregar el valor en billetes.

ejemplo:

320/500=0.64 siguiente
320/100=3.2. Coges la parte entera 3 y lo multiplicas por 3*100=300
usando la función modulo recoges el resto y sigues iterando por abajo
20/50=0.4 siguiente
20/20=1 coges la parte entera y revisas nuevamente el modulo de la operación, como da cero se da por finalizado y ya se puede terminar.

Eso es lo que se debe hacer siempre. Se debe tener igual en cuenta los casos en que no se puede entregar los billetes

ejemplo 263 euros, en ese caso se le debe advertir al usuario que no es posible entregar esta cantidad porque no se tienen billetes disponibles.

Espero hayas entendido la dinámica del ejemplo y lo programes. Creo que no es muy complicado.

[tete69]

Gracias, pero viene a ser lo mismo que el algoritmo que planteo arriba. Fijate, por ejemplo, en un caso como el que expongo al final del post:

billetes disponibles{200,50,20}
n=210

La solución es 3x50 + 3x20, pero siguiendo tu método, o el mío, el resultado es 1x200, y el 10 restante desaparece. Por eso digo que habrá que usar recursividad.

A propósito, no es un trabajo de universidad xD. Estoy en 2º de Bachillerato, y es mi trabajo de fin de curso.

[cuasatar]

Pues es cuestión de colocar otro condicional. Siguiendo el mismo ejemplo los billetes de 200,50,20 y la cantidad a entregar de 210 como ya se descarto que sirva el de 200 se debe evaluar la siguiente opción (es decir 50). Si la división es mayor que 1 se debe poder hacer un condicional para que revise todos los casos posibles (es decir con 4,3,2 y 1 billetes). En caso de que no encuentre con la primera opción 4, pase a la 3, la 2 y finalmente la 1. Si en alguna iteración encuentra la respuesta se detiene sino continua evaluando.

210/50=4.2
10/20=no sirve

se sigue entonces con la siguiente opción que es restar la parte entera de la división anterior en una unidad
210/(3*50)=60
60/20=3

Y se soluciona el problema. Yo lo haria usando do while (que de momento se me ocurre para evaluar y que siga entrando a la función mientras se cumplan las condiciones, en el momento en que no se cumplan las condiciones se sale)

Quizas tambien se pueda hacer recursivamente pero de momento no se me ocurre alguna forma.