| Título: | Comparativo entre a estratégia gulosa e a programação dinâmica para o problema do troco com sistemas de moedas canônicos |
| Autor(es): | Mattioli, Lucas Vasconcelos |
| Orientador(es): | Costa Júnior, Edson Alves da |
| Assunto: | Algoritmos de computador
Programação dinâmica |
| Data de apresentação: | 11-Dez-2018 |
| Data de publicação: | 28-Fev-2019 |
| Referência: | MATTIOLI, Lucas Vasconcelos. Comparativo entre a estratégia gulosa e a programação dinâmica para o problema do troco com sistemas de moedas canônicos. 2018. 59 f., il. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Software)—Universidade de Brasília, Brasília, 2018. |
| Resumo: | O problema do troco é uma especialização do problema da mochila, sendo possível resolvêlo
com um algoritmo de programação dinâmica. É possível, também, resolver o problema
utilizando um algoritmo guloso quando o sistema de moedas do problema é canônico.
Este trabalho analisa e compara os tempos de execução dos algoritmos de programação
dinâmica, guloso e de um algoritmo de determinação da canonicidade em cima de sistemas
de moedas gerados pseudo-aleatoriamente. Os algoritmos foram implementados e seus
tempos mensurados na linguagem de programação C++, seguindo o padrão C++14. Foi
verificado que, apenas para sistemas de moedas com tamanhos pequenos (até 76 moedas),
o algoritmo de programação dinâmica se mostra mais eficiente que os algoritmos guloso e
de determinação de canonicidade, este necessário para garantir a canonicidade do sistema
e assegurar a correção do algoritmo guloso. |
| Abstract: | The coin change problem is a specialization of the knapsack problem, being possible to
solve it with a dynamic programming algorithm. It is also possible to solve the problem
using a greedy algorithm when the coin system is canonical. This work analyzes and
compares the execution times of dynamic programming, greedy and canonicity determination
algorithms on top of pseudo-randomly generated coin systems. The algorithms
were implemented in the C++ programming language, following the C++ 14 standard.
It was verified that, solely for coin systems with small sizes (up to 76 coins), the dynamic
programming algorithm is more efficient than the greedy one, along with the canonicity
determination algorithm, which is used to guarantee the canonicity of the system and
enable the use of the greedy algorithm. |
| Informações adicionais: | Trabalho de Conclusão de Curso (graduação)—Universidade de Brasília, Faculdade UnB Gama, 2018. |
| Aparece na Coleção: | Engenharia de Software
|
