Joaquim juntou em seu cofre uma quantia de R$ 137,00 em moedas e deseja trocar esse valor em notas do sistema monetário brasileiro. Qual é a quantidade mínima de notas que Joaquim

Gabarito

Certo

Comentário do professor

Usamos a estratégia gulosa: sempre trocar pelo maior valor possível. Primeiro retiramos R$100, sobrando \(137-100=37\). Em seguida, uma nota de R$20, sobrando \(37-20=17\); uma de R$10, sobrando \(17-10=7\); uma de R$5, sobrando \(7-5=2\); e finalmente uma de R$2, sobrando \(2-2=0\).

Assim obtemos as notas: 100, 20, 10, 5 e 2, totalizando \(1+1+1+1+1=5\) notas.

Para ver que não é possível com menos de 5 notas, considere os casos com 4 notas: se houver R$100, as outras três teriam que somar 37 — não existe combinação de três notas (apenas 20,10,5,2) que dê 37; se houver duas R$50, as duas restantes teriam que somar 37 — impossível; sem 50/100, quatro notas de até 20 somam no máximo 80 < 137. Logo, 5 é o mínimo.