We now prove the simple greedy algorithm for the coin change problem with quarte

Question

We now prove the simple greedy algorithm for the coin change problem with quarters, dimes, nickels and pennies are optimal (i.e. the number of coins in the given change is minimized), when the supply of each coin type is unlimited. Let q0, d0, k0, p0 be the number of quarters, dimes, nickels and pennies used for changing n cents in an optimal solution.

1. First, show that d0 2, k0 1, p0 4. Also, show that if k0 = 1, then d0 1.

2. Now show it is always optimal to choose as many quarters as possible.

3. Finally, show that the greedy algorithm is optimal in its choice for dimes, nickels and pennies.

Explanation / Answer

A1.
Greedy algorithm: we will always use greatest valued coins as many as possible without exceeding the total amount, and then after deducing that sum from total amount we will use remainder as new existing amount and repeat the above process.
Penny = 1 cent
nickel = 5 cent
Dime = 10 cent
Quarter = 25 cent
Suppose that we can only choose from penny and nickels, then in that case we can use max 4 pennies because if our amount becomes 5 or greater than 5 then I will convert it into 1 nickel. This prove that pennies will always be less than 4 (P<= 4)
Now Suppose that we can only choose from penny nickels and dimes, then in this case we can use maximum 1 nickel because if we use 2 nickels then it would be optimal if we use 1 dime rather than 2 nickels. this prove that nickels will always be less than or equal to 1.(k <=1)
Now suppose that we can choose only from penny nickels, dime and quarters, then in this case we can use maximum two dime because if we use 3 dimes than it would be optimal if we use one nickel and one quarter rather than three dime, which proves that dimes will always be less that or equal to 2.(d <=2)
which proves that if we have these four types of coins than:
p<=4 & k<=1 & d<=2
A2.
Now if we fixed the amount of nickels (k = 1) then amount of dimes will always be less than or equal to 1.
As we have proved in first part that our number of nickels will always be less than or equal to 1.
when n < 10, then we will use one nickel and rest of amount in pennies and in this case total dime will always be zero.
when 10 <= n < 15, then we will use 1 dime but no nickels.
when 15 <= n < 20 then we will use 1 dime and one nickel and rest of the amount in pennies.
when 20 <= n < 25 then we will use two dimes but nickels and rest of the amount in pennies.
for n => 25 then we will use n quarters and rest of the amount which will be less than 24 can be used from above scenarios.
So we can say that in each case no. of nickel coin is fixed to 1, then dimes will always be zero or 1.
B.
Now if we choose two coins (r, s), where s > r
Now if we have to choose coins for amount 'c' cents, then any number which is larger than s will be replaced by 1 's' coin and rest of the amount in lower denominations. further whenever we will have remainder of c/s > s then I will use as many possible s coins before considering lower denominations coins. So it will always be optimal to choose as many quarters as possible.
C.
If we have only dime, nickel and pennies than which valued as (10, 5, 1) Since these numbers are co-prime. it will be optimal to choose greedy algoritham to calculate number of coins. Because it would be optimal to use one dime rather than two nickel to use least amount of coins.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.