Making Change: 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 ith 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
71
The objective is to minimize the number of coins returned or:
a) Describe and give pseudocode for a dynamic programming algorithm to find the minimum number of coins to make change for A.
b) What is the theoretical running time of your algorithm?
71