Problem 5: Making Change Implementation

We wish to make change for an amount using as few coins as possible using an algorithm. You may use any language you choose to implement your DP change algorithm. 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. Example amount.txt: 1 2 5 10 1 3 7 12 29 1 2 4 8 15 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. Example change.txt: 1 2 5 10 0 0 2 2 1 3 7 12 29 0 1 2 1 4 1 2 4 8 15 1 1 1 1 4 In the above example, to make 29 cents change from the denomination set (1, 3, 7, 12) you need 0: 1 cent coin, 1: 3 cent coin, 2: 7 cent coins and 1: 12 cent coin for a total of 4 coins.