Making Change: Given coins of denominations (value) 1 = v1 < v2< … < vn, we wish
ID: 3878898 • Letter: M
Question
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
Explanation / Answer
Answer:
a)
M(j) = the minimum number of coins required to make change for an amount of money j
M(j) = min{M(j vi )} + 1
The smallest number of coins required to make j , is the smallest number required to make j vi , plus one.
Algorithm Minimum-Change(C,v)
//all of vi and C are positive integers.
Input: n types of coin denominations of values v1 < v2 < ... < vn
Output: The minimum number of coins required to make change for an amount of money j
M[0]ß0
{M[j] where i<0}
for jß1 to C do
Min
for iß1 to |V| do
if M[j-v[i]] +1< min then
minßM[j-v[i]] +1
end if
end for
return M[C]
end for
b)
The theoretical running time of the above algorithm is O(n * A)
Please provide your valuable feedback.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.