Programação Dinâmica – problema do Mínimo de Moedas

Olá pessoal,

Dando continuidade ao estudo de programação dinâmica preparei mais uma aplicativo. Desta vez para solucionar o problema de Mínimo de Moedas.

Enunciado do problema:

Qual o número mínimo de moedas para fazer um troco?
Encontre um algoritmo que consiga determinar o número mínimo de moedas para um certo valor em tempo polinomial.
Verifique como solucionar o problema usando programação dinâmica!!!
Supomos que conhecemos as moedas disponíveis e que sempre existe moeda de 1 centavo (unidade monetária).

Montei uma aplicação para comparar o tempo computacional de algoritmo convencional que utiliza força bruta, isto quer dizer testam todas as possibilidades repetidas vezes, com algoritmo guloso e algoritmo modelado com programação dinâmica .

Acreditem o resultado é surpreendente!!! O algoritmo guloso tem desempenho muito superior a solução com programação dinâmica e principalmente com força bruta. Isso pode ser percebido apenas para valores muito grandes (exemplo 99000 centavos).

O código foi todo escrito em C# e deixei um botão para você poder copiar os métodos utilizados.

A figura abaixo ilustra o aplicativo, que está disponível no Dropbox. Basta clicar na imagem para ser redirecionado.

Programação Dinâmica – Problema: Mínimo de Moedas

Programação Dinâmica – Problema: Mínimo de Moedas

Se preferir, pode baixar todo o código fonte clicando aqui.

Esse aplicativo foi desenvolvido como atividade complementar e voluntária do meu curso de doutorado, minha única intenção é compartilhar conhecimento.

Espero que gostem!

Um abraço,

Prof. Leandro

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: