Solução Troco

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

 

Este é um problema clássico de Programação Dinâmica. Assim como no Knapsack (com solução aqui), ou Pontes de São Petesburgo (com solução aqui), vamos testar todas as possibilidades olhando, para cada moeda, se ela deve ou não ser inserida no troco. Vamos criar uma tabela de PD int matriz[1010][100010] que guardará os estados já calculados, e usaremos uma função recursiva de nome busca para calcularmos todos os estados na abordagem Top-Down. Vamos salvar o valor de cada moeda no vetor int moeda[1010], e guardar o char resposta que começará com valor 'N'.

A função será bem simples: ela receberá a moeda que estamos olhando (int coin) e soma que já temos das moedas passadas que colocamos no troco (int soma). Se já tivermos calculado a PD para tal estado, a função retorna. Caso contrário, marcamos esse estado na tabela de PD. Verificamos agora se soma já é o valor desejado (soma==n). Se for, fazemos a variável resposta receber 'S' e retornamos a função. Se não for ainda, continuamos a função. Se já tivermos olhado todas as moedas (coin >n) ou a soma já tiver superado o valor desejado (soma>v), a função retorna. Caso contrário, chamamos a função colocando e não colocando a moeda: colocar é chamar para a próxima moeda adicionando o valor da atual a soma ("busca(coin+1, soma+moeda[coin]);") e não colocar é chamar para a próxima com a mesma soma que tínhamos na atua ("busca(coin+1, soma);").

Se chamarmos a função para a primeira moeda, ela testa todos os casos necessários. Se em algum momento tivermos encontrado um conjunto de moedas com o valor desejado, a variável resposta terá o valor 'S' e, caso contrário, não terá sido alterada e ainda guardará o valor 'N'. Logo, basta imprimí-la. Segue o código comentado para melhor entendimento.

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: