This is the first mandatory assignment of the course DTE-2501 AI Methods and Applications. It is about dynamic programming.
Instructions: Solve the problem using Python. In addition to the code, you are also required to write a short (<1 page) pdf report where you briefly describe your work.
Problem: Given a sum s = 1 040 528 NOK and the 4 Norwegian coins with denominations {1, 5, 10, 20}, write a dynamic programming algorithm in Python using the tabular approach that outputs the minimum number of coins that sum up to s.
- Identify the subproblems and write the recurrent relation (Include the answer in your report)
- Write the program that solves the problem described above. Your program should print out the result. (Include the result in your report)
Note that your code should be readable, and commented on in such a way that a reviewer with a programming knowledge can understand how it works. This assignment is individual therefore the code must be your own original work.