1

Coins have a value of ci, for every i ≥ 0, for some integer constant c > 1. For example, if c = 3, you have coins with values 1 (= 30), 3, 9 (= 32), 27, ...

You need to design an algorithm that, given an integer value n, makes change for n using the fewest number of coins. You can assume that there is an unlimited supply of coins of each denomination ci with ci ≤ n.

I've come up with the greedy algorithm, but I'm stuck on this question:

Show that any optimal solution has at most c − 1 coins of value ci, for any i.

I get it, and I see how it works, but I don't know how to verbalize/show it. Can someone please point me in the right direction?

Improve this question
3
  • 1
    in this case it's pure math (for the CS side: it's usually a dynamic programming problem if the coins are not greedy ;)) - the trick here is to see that the way the coins are given is very similar to the way you represent numbers to base c ;) ... Commented Feb 3, 2016 at 6:15
  • 1
    If there are c coins of value c^i, you can replace them with one coin of value c^{i+1}. Thus the solution cannot be optimal. Commented Feb 3, 2016 at 6:17
  • The proof is very simple. Assume there is an optimal solution s* that uses more than c-1 coins of values c^i for some i. Then you can replace c coins of value c^i with a single coin of value c^{i+1}, thereby reducing the number of coins by c. But then s* cannot be an optimal solution. A contradiction. Commented Feb 3, 2016 at 11:31

1 Answer 1

Reset to default
4

Often, greedy algorithms can be proven correct by showing that if there is an (allegedly) optimal solution whose structure is different from what would be produced by your algorithm, you can change it to what your algorithm would have produced and show that the result is as good or better.

In this case: Assume (for the sake of contradiction) that there is an optimal solution that uses c or more coins of value ci. Then, how could you improve that solution in the manner of the greedy algorithm (thus showing that solutions that do things differently are, in fact, not optimal?)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.