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
Your thought experiment for the day
Author
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:
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?
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]
That's probably wrong, but it's Friday. I don't wanna use my brain anymore, while still superficially looking like I am. [grin]
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
Author
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).
Author
Quote:Original post by SiCraneJust trying to provoke discussion. :-) I wasn't aware of the paper, though.... feel free to post it here when discussion dies down some.
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
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.
This can be done with dynamic programming.
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.
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.
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.
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.
Author
Quote:Original post by hplus0603Does it? 10 does not divide 25 evenly.
The reason it works for US coins is that each coin evenly divides the coin above it, except for the topmost coin.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement