1. You are working as a cashier in a country that uses different denominations o
ID: 3597221 • Letter: 1
Question
1. You are working as a cashier in a country that uses different denominations of coins than we are used to in the US (1, 5, 10, and 25). Design an efficient, dynamic programming, algorithm that will solve the problem of finding the smallest number of coins required to make change. You must write pseudo-code for both a memoized version, AND, an iterative version. Your algorithm will take the following as input: . denom: an array containing the denominations of all coins . d: the number of different denominations n: the number of cents to make change for · You may assume that the smallest denomination of coin is one, so there is always some way to make change for every n. Hint: try selecting each denomination of coin in turn, then form change for the remaining cents. For example, when n-9 and denom-f1, 4, 6/, you could make 9 cents by adding a one-cent coin to the coins that add up to 8 cents, a four-cent coin to coins that add up to 5 cents, or a six-cent coin to coins that add up to 3 cents. In particular, C(n) represents the fewest number of coins needed to make n cents, C(9) = 1+minJC(8), C(5), C(3), in this case. We can apply the same strategy to any number and denominations of coins giving us the recurrence: C(n)-1 + min(C(n-denom[i]}), denom [i] nExplanation / Answer
If we are looking for minimum number of coins of given denominations to adjust for a given amount e then we can use following approach:
We will take up the highest denominnation (i.e 25) and divide the amount by it if the amount is more than the 25. Then we
will repeat the same step for the remainder till we get the remainder zero. At every step we will be getting the number of coins of different denominations
A pseudocode can be:
while (amount > 0){
if (amount > 25){
n25 = amount / 25 //n25 represent the number of coins having value 25
amount = amount % 25
continue
}
if (amount > 10){
n10 = amount / 10 //n10 represent the number of coins having value 10
amount = amount % 10
continue
}
if (amount > 5){
n5 = amount / 5 //n5 represent the number of coins having value 5
amount = amount % 5
continue
}
if (amount > 1){
n1 = amount //n1 represent the number of coins having value 1
amount = 0;
continue
}
n = n25+n10+n5+n1;
}
A recursive way can be :
int count(int amt, int deno){
if (deno == 1 && amt < 5)
return amt;
if (deno == 5 && amt < 10)
return amt/5 + count(amt % 5,1);
if (deno == 10 && amt < 25)
return amt/10 + count(amt % 10,5);
if (deno == 25 && amt > 25)
return amt/25 + count(amt % 25,10);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.