Boa noite.
Estou a desenvolver um programa que permite calcular o menor troco através de uma série de moedas disponíveis, por exemplo:
troco = 24
moedas = {20,12,1}
A solução devia ser 2 moedas de 12.
Numa primeira fase implementei uma solução que apenas verificava se era possível dar troco e que não calculava o menor número de moedas com que se podia fazer esse troco, para isso usei o seguinte código.
public static int [] calcula(int troco,int [] moedas){
int i =0;
int [] nmoedas =new int [moedas.length];
while(moedas[i]!=0){
if (troco >= moedas[i]){
troco = troco - moedas[i];
nmoedas[i]=nmoedas[i]+1;
}
else{
if((moedas[i+1]==0) && (troco !=0))
nmoedas[i]++;
i++;
}
}
return nmoedas;
}
Agora tenho que implementar uma solução usando recursividade e que já devolva a solução onde o número de moedas a dar como troco é menor, mas não estou a conseguir fazer.
Já vi o seguinte tópico http://www.portugal-a-programar.org/forum/index.php?topic=22825.0 onde o problema é parecido com o meu mas continuo sem perceber muito bem uma vez que na solução que foi desenvolvida nesse tópico não percebo certas partes do código. Se alguém conseguir dar uma ajuda agradecia.
Cumprimentos.