• Advertisement

• ### Popular Now

• 15
• 15
• 11
• 9
• 10
• Advertisement
• Advertisement
• Advertisement

# Your thought experiment for the day

This topic is 4878 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

The US currency system has 4 coins that are most commonly used, in denominations of 1 cent, 5 cents, 10 cents, and 25 cents. (Other denominations are also available but are much rarer in general circulation.) This set of denominations, {1, 5, 10, 25} has the interesting property that a particular amount of money can be expressed in a minimal total number of coins with this algorithm:
procedure make_change(amount)
for each denomination d in decreasing order (25, 10, 5, 1)
while(amount >= d)
dispense coin of denomination d
amount = amount - d
end while
end for
end


Consider other possible denomination sets. One such set is {1, 5, 7}. The algorithm above does _not_ produce the minimal number of coins for 10 cents: it favors 4 coins (1, 1, 1, 7) where only 2 (5, 5) are necessary. Your challenges, should you choose to accept them: 1. Is there an efficient algorithm (I.E. not NP-hard) to determine whether the above algorithm is suitable for a given set of denominations S? 2. Is there an efficient algorithm (I.E. not NP-hard) to determine correct change for any denomination and any amount?

#### Share this post

##### Share on other sites
Advertisement
Being lazy and taking a stab at number 1 without thinking it through much, I'd say that as long as each coin amount is greater than or equal to twice the next largest one smaller than it, then the algorithm works. So, because 5 >= 1·2, 10 >= 5·2, and 25 >= 10·2, the set {1, 5, 10, 25} works this way.

That's probably wrong, but it's Friday. I don't wanna use my brain anymore, while still superficially looking like I am. [grin]

#### Share this post

##### Share on other sites
If you're actually looking for the answers, I can point you to a paper that gives you your answers. If you're just trying to provoke discussion, then I'll probably have to sit this one out. :P

#### Share this post

##### Share on other sites
Hmm... but consider the coin set {16, 5, 1}. Your rule holds, but the amount 20 is expressed by the algorithm as (1, 1, 1, 1, 16) instead of (5, 5, 5, 5).

#### Share this post

##### Share on other sites
Quote:
 Original post by SiCraneIf you're actually looking for the answers, I can point you to a paper that gives you your answers. If you're just trying to provoke discussion, then I'll probably have to sit this one out. :P
Just trying to provoke discussion. :-) I wasn't aware of the paper, though.... feel free to post it here when discussion dies down some.

#### Share this post

##### Share on other sites
2. Is there an efficient algorithm (I.E. not NP-hard) to determine correct change for any denomination and any amount?

This can be done with dynamic programming.

#### Share this post

##### Share on other sites
just blue-skying it here...

seems the original algorithm fails when there is a jump of less than 2x (5 to 7).

maybe define cost as "(n integer_div d) + (n modulo d)" and pick the lowest cost denomination for each step?

otherwise, if my 1st guess is right (the 2x thing), you may need some king of grouping. Start with the highest value, and group until you get a value of < 0.5*highest. Start over with the new value, etc.

#### Share this post

##### Share on other sites
The reason it works for US coins is that each coin evenly divides the coin above it, except for the topmost coin. Thus, there is a never a problem of dividing into N of one or N*M of the other.

#### Share this post

##### Share on other sites
Dynamic programming solves the problem of finding the minimal number of coins in O(N*M) time and O(N+M) memory, where N is the number of different demoninations of coins and M is the number you wish to find change for. You can test this algorithm against the original algorithm for each M >= 0 until you find L consecutive numbers whose minimal coin set all have a coin of value L, where L is the largest coin denomination (though the proof that this will always happen is a little more complex). This will determine the correctness of the greedy algorithm in polynomial time.

#### Share this post

##### Share on other sites
Quote:
 Original post by hplus0603The reason it works for US coins is that each coin evenly divides the coin above it, except for the topmost coin.
Does it? 10 does not divide 25 evenly.

#### Share this post

##### Share on other sites

• Advertisement