Problem 3. (10 pts) Given arbitrary amount of money, you want to make change usi

Question

Problem 3. (10 pts) Given arbitrary amount of money, you want to make change using the fewest number of coins. The value of each coin is a positive integer (a) Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c for some integers e 1 and k 21. Show that the greedy algorithm always yields an co,ci,2,..., optimal solution: you need to write down the algorithm (cf lecture notes), so that we would know which algorithm you are referring to in your proof. (b) Consider the set of coins consisting 50 cents, 15 cents, 10 cents, 2 cents and 1 cent. Does greedy algorithm yield an optimal solution for this set of coin? Justify your answer.

Explanation / Answer

a). Let’s consider the first two types of coins in this set, pennies and coins that are worth c cents each, which we will call cˆ. At most, we can use c 1 pennies because any number larger than c pennies would be replaced by at least one cˆ coin. This operation would reduce the total coin number by c 1. In other words, when the remainder is greater than c and I’m allowed to use only pennies and cˆ coins, I would use as many cˆ coins before considering pennies.

2. The same thoughts apply for larger coins. Let’s consider cn-1 and cn coins. At most, we can use c 1 cn-1 coins. Because any number larger than n c would be replaced by at least one cn coin. This operation would reduce the total coin number by c 1. In other words, when the remainder is greater than cn and I’m allowed to use only coins that are worth less than cˆn , I would use as many n cˆ coins as possible before considering other coins.

3. Combining the first two arguments, the greedy algorithm applies to all the levels of this particular coin set denomination.

b)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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