Consider the problem of making change for n centsusing the least number of coins

Question

Consider the problem of making change for n centsusing the least number of coins. Suppose that the available coinsare in the denominations c0, c1, ...,ck for some integers c > 1 and k>= 1. Show that the greedy algorithm always yields an optimalsolution.

1. Hint: Note that you can prove optimality in avariety of ways. Here I am suggesting one possibility.
   
   You can prove by contradiction. The comparison of the greedysolution to the optimal solution can proceed along the lines of thefractional knapsack problem. You will of course need to useadditional facts:
   • (c0 + c1 + c2 + ... +ci)*(c-1) = ci+1 - 1
   • c*ci = 1*ci+1
     Therefore, number of coins of any one denomination in the changethat is made should be less than c for otherwise we can replace cof those coins with one coin of the next higher denomination.

Consider the problem of making change for n centsusing the least number of coins. Suppose that the available coinsare in the denominations c0, c1, ...,ck for some integers c > 1 and k>= 1. Show that the greedy algorithm always yields an optimalsolution.

1. Hint: Note that you can prove optimality in avariety of ways. Here I am suggesting one possibility.
   
   You can prove by contradiction. The comparison of the greedysolution to the optimal solution can proceed along the lines of thefractional knapsack problem. You will of course need to useadditional facts:
   • (c0 + c1 + c2 + ... +ci)*(c-1) = ci+1 - 1
   • c*ci = 1*ci+1
     Therefore, number of coins of any one denomination in the changethat is made should be less than c for otherwise we can replace cof those coins with one coin of the next higher denomination.

Explanation / Answer

1. Let’s consider the first two types of coins in thisset, pennies and coins that are worth c cents each, which we willcall cˆ . At most, we can use c -1 pennies because any numberlarger than c pennies would be replaced by at least one cˆcoin.

This operation would reduce the total coin number by c -1. Inother words, when the remainder is greater than c and I’mallowed to use only pennies and cˆ coins, I would use as manycˆ coins before considering pennies.

2. The same thoughts apply for larger coins. Let’sconsider cˆ n-1 and cˆncoins. At most, we can use c -1 cˆn-1 coins.Because any number larger than cn would be replaced by at least onecˆn coin. This operation would reduce the totalcoin number by c -1. In other words, when the remainder is greaterthan cn and I’m allowed to use only coins that areworth less than cˆn , I would use as manycˆn coins as possible before considering othercoins.

3. Combining the first two arguments, the greedy algorithmapplies to all the levels of this particular coin setdenomination.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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