Python | Dynamic Programming Algorithm Implementation Given coins of denominatio

Question

Python | Dynamic Programming Algorithm Implementation

Given coins of denominations (value) 1 = v1 < v2< … < vn, we wish to make change for an amount A using as few coins as possible. Assume that vi ’s and A are integers. Since v1= 1 there will always be a solution.

Formally, an algorithm for this problem should take as input:

·        An array V where V[i] is the value of the coin of the i th denomination.

·        A value A which is the amount of change we are asked to make

The algorithm should return an array C where C[i] is the number of coins of value V[i] to return as change and m the minimum number of coins it took. You must return exact change so:

The objective is to minimize the number of coins returned or:

The program should read input from a file named “amount.txt”. The file contains lists of denominations (V) followed on the next line by the amount A:

In the above example the first line contains the denominations V=(1, 2, 5) and the next line contains the amount A = 10 for which we need change. There are three different denomination sets and amounts in the above example. A denomination set will be on a single line and will always start with the 1 “coin”.

The results should be written to a file named change.txt and should contain the denomination set, the amount A, the change result array and the minimum number of coins used.

Explanation / Answer

main.py

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.