A study on ’The Change-Making Problem’
It is widely known that many computationally-demanding problems require more efficient solutions than to simply search exaustively for the answers. This is particularly true for tasks that execute repeated operations in considerable amounts of times.
This project focuses on the famous challenge called ’The Change-Making Problem’ and presents a study on the computational performance of dynamic programming algorithms for solving such problem.
The implemented algorithms were 3, and they all follow the same base strategy to tackle the issue so that a high fidelity comparison could be analysed.
/report - documentation on the conducted study
/results - outputs produced by the implemented code
/src - source code of the algorithms
Plot presenting the evolution of the (average) execution times of the 3 algorithms for the same input change amount, suggesting that the dynamic-programming-based implementation is for efficient that the others.
$ cd src
$ pip3 install -r requirements.txt
$ python3 TheChangeMakingProblem.pyThe author of this repository is Filipe Pires, and the project was developed for the Advanced Algorithms Course of the master's degree in Informatics Engineering of the University of Aveiro.
For further information read the report or contact me at [email protected].