Estou com a mesma dúvida, não consigo montar o algoritmo pra mim algumas coisas não fazem sentido. Mesmo assim eis a resposta que o monitor me deu:
Pode usar o algoritmo "guloso", que pode não funcionar em todos os casos, como o rpfessor deve ter dito em aula, mas vai funcionar nos casos de teste que serão utilizados na correção.
Esse algoritmo funciona assim:
1) Comece com a nota de maior valor, e ache quantas dessas notas "cabem" no troco. Por exemplo, se o troco é R$25,00 e a nota de maior valor R$10,00, "cabem" duas dessas notas no troco. Tem que lembrar de ver quantas notas tem no caixa. Se couberem duas, mas só tiver uma no caixa, só pode usar uma.
2) Uma vez descoberto qtas notas desse valor vai usar, retire do troco o valor total que vc vai dar em troco nessa nota. No exemplo anterior, se vc tiver duas notas de R$10,00, você precisa retirar 2*R$10,00 do troco, sobrando R$5,00.
3) Repita o procedimento (1) e (2) para as notas (e moedas) seguintes, sempre atualizando o valor do troco.
No final vc deve ter o troco em notas mínimas.
Repetindo, esse algoritmo não funciona em 100% dos casos, mas será considerado correto nesse EP.