2. Let An = { a1, a2...., an } be a finite set of distinct coin types (e.g., a1=

Question

2. Let An = { a1, a2...., an } be a finite set of distinct coin types (e.g., a1= 50 cents, a2= 25 Cents, a3= 10 cents etc.). We assume each ai is an integer and that a1 > a2 > ? > an. Each type is available in unlimited quantity. The coin changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0. (a) Assume an = 1, a greedy solution to the problem will make change by using the coin types in the order a1,a2, ?, an. When coin type ai is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy. (b) Give a counterexample to show that the algorithm in (a) doesn't necessarily generate solutions that use the minimum total number of coins.

Explanation / Answer

Answer:

(a) The Greedy algorithm for making change of the largest denomination from a single coint that can be taken at a time is given as follows:

MAKE_CHANGE(M):

            for i <- k to -1 do

                        while M >= ai

                                    count[i] <- count[i] + 1

                                    M <- M - ai

The above algorithm runs at O(C+k) where C is the number of coins in the greedy solution.

(b)

Consider a simple example, {25, 10, 1}. According to problem, if need to make the change of 30 cents, then the greedy solution will first take a quarter, followed by 5 pennies, a total of size coins. But the actual solution will be consisting of 3 dimes.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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