programa para una cajera de banco

[andre22rz]

HOLA A TODOS: quisiera saber si me pueden ayudar con esta tarea que me dejaron, hasta ahora estoy empezando en el tema de la programacion y por mas que le doy vueltas al problema no le hallo una solucion . . . no les pido que me solucionen la tarea, por favor con una clave o una formula es suficiente....GRACIAS

un programa que indique a una cajera de banco el
número y denominación de los billetes que necesita darle a un cliente al hacer un
retiro. La cajera deberá darle al cliente billetes de la más alta denominación posible,
esto es, el menor número de billetes. Suponga que los retiros deben de ser en
cantidades múltiples de 10 pesos y que hay billetes de $10, $20, $50 y $100 pesos.

[Ronruby]

Hmmmm ... Tengo un algoritmo rondando por ahi para eso mismo. Greedy Algorithm.
Lo busque pero no lo encontre ... bueno, la idea es hacer uso del operando % que significa modulus, el restante de una division.

¿Como usarlo?
NOTA: EL CODIGO ES EN PHP, PERO ES FACIL PASARLO A JAVA (CREI QUE HABIA POSTEADO ESTO EN PHP)

Código PHP:

Digamos que el usuario solicita 1460, haces:
$billetes100 = $cantidad%100; // devolvera 14
$cantidad = $cantidad - ($billetes100*100);
$billetes50 = $cantidad%50; //devuelve 1
$cantidad = $cantidad - ($billetes50*50);
$billetes20 = $cantidad%20; //devuelve 0
$cantidad = $cantidad - ($billetes20*20);
$billetes10 = $cantidad%10; //devuelve 1
 

Total: 14 billetes de 100, 1 de 50, 1 de 10.

Ahora bien, asi como te lo mostre es un ejemplo. La forma en que lo implemente fue poniendo las papeletas en un array y use un bucle while para hacerlo mas "automatizado" y "bonito" el codigo.

EDIT: Lo encontre rondando en mi correo, obvia las partes que no son necesarias:

Código PHP:

<?php
 
function greedyAlgorithm($cantidad, $papeletas = null) {
    $resto = $cantidad;
    $i = 0;
    
    while($resto != 0) {
        $nuevas[$papeletas[$i]] = floor($resto/$papeletas[$i]);
        $resto %= $papeletas[$i];
        $i++;
    }
    
    return $nuevas;
}
 
$nuevas = greedyAlgorithm(1460, array(100,50,20,10));
 
echo '<pre>';
var_dump($nuevas);
echo '</pre>';
 
?>
 

Resultado:

array(4) {
[100]=>
float(14)
[50]=>
float(1)
[20]=>
float(0)
[10]=>
float(1)
}