Tal y como yo lo veo, la cosa sería ver cuántos billetes de 1000 entran en esa cantidad dada, y luego trabajar con el resto de la misma manera: cuántos billetes de 500 entran en el resto, luego cuántos billetes de 200 entran, luego de 100, luego de 50, ... hasta llegar a la cantidad final.
Puedes usar las instrucciones div y mod para ello.
Un saludo.
Edito: justamente lo que te ha explicado
roman encima de mi mensaje
.