All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Intuitive Coins (Posted on 2005-03-29) Difficulty: 3 of 5
If you must pay an amount in coins, the "intuitive" algorithm is: pay as much as possible with the largest denomination coin, and then go on to pay the rest with the other coins. For example, if there are 25, 5 and 1 cent coins, to pay someone 32 cents, you'd first give him a 25 cents coin, then one 5 cent coin, and finally two 1 cent coins.)

However, this doesn't always end paying with as few coins as possible: if we had 25, 10 and 1 cent coins, paying 32 cents with the "intuitive" algorithm would use 8 coins, while three 10 cent coins and two 1 cent coins would be better.

We can call a set "intuitive", if the "intuitive algorithm" always pays out any amount with as few coins as possible.

The problem: give an algorithm that allows you to decide that {25,5,1} is an "intuitive" set, while {25,10,1} isn't.

See The Solution Submitted by Federico Kereki    
Rating: 3.8000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
intuitive enough | Comment 6 of 14 |
I think it's enough intuitive the criterion of "divisibility": each coin has to be multiple of the inmediat precedent in the sequence of coins, because in this case it's always convenient to chose the higher coin.
  Posted by armando on 2005-03-30 13:21:39
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information