Python | Dynamic Programming Algorithm Implementation

Given coins of denominations (value) 1 = v₁ 2n, we wish to make change for an amount A using as few coins as possible. Assume that v_i s and A are integers. Since v₁= 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.