Coin Change problem: Given a positive integer n, we consider the following probl

Question

Coin Change problem:

Given a positive integer n, we consider the following problem: Making change for n cents using the fewest number of coins. Assume that the value of each coin is a positive integer.

(a) Describe a greedy algorithm to make change consisting of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent). Prove that your algorithm yields an optimal solution to the given make change problem.

(b) Suppose that the available coins are in the denominations that are powers of C; that is, the denominations are C0 , C1 , . . . , Ck for some integers C > 1 and k 1.

Show that the greedy algorithm always yields an optimal solution to the given make change problem.

(c) Give a positive integer n and a set of coin denominations for which the greedy algorithm does not yield an optimal solution to the given make change problem. Your set should include a penny so that there is a feasible solution for every value of n.

Explanation / Answer

a)
If n < 5, use n pennies.
If 5 n < 10, use 1 nickels and n 5 pennies
If 10 n < 25 use bn/10c dimes, and then one of the 2 previous cases for n 10bn/10c
If 25 n, use bn/25c quarters, and then one of the 3 previous cases for n 25bn/25c.

>Let Sk be the optimal solution when there are k types of changes. when k = 3, we have dimes, nickels and pennies for change. To obtain the solution of k + 1 types of changes, a greedy choice of using the largest change first will yield optimal solution k+1.
>This is because for all k + 1 types of changes (excluding pennies), they have the greatest common divisor of 5. In other words, an optimal solution can always be obtained by merging small changes to large changes (e.g., one dime = two nickels)

b)
Let solution Sk1 be the optimal when there are c0, c1, · · · , ck1 denominations. Making a greedy choice for ck will yield optimal solution for Sk. This is because all c0, c1 , · · · , ck are commonly divisible by c.
Thus, for any non-optimal solution, it can be migrate to optimal solution Sk by merging changes from ci to c j, where j > i

c)
n=54, c0 = 1, c1 = 27 and c2 = 50

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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