Greetings Readers,
after an hour of thinking, I found a solution to get rid of all those small coins that piled up in my pocket: Carry the coins 1Ct, 2Ct, 2Ct, 5Ct, 10 Ct, 20Ct, 20Ct, 50Ct, 1Eur, 2Eur, 2Eur with you and apply the optimal algorithm for giving out fractions beyond whole Euros with efficient access!
Let me elaborate more. I have been lazy about getting rid of my small coins and thus, a large amount of coins has accumulated. This large pile has the ability to bust out of the part of my purse that is supposed to contain them without a single problem. In fact the pile grew big enough to be a problem when just contained in the pocket! Clearly, a solution is required.
Just searching through the large pile of coins in order to find the correct coins to give out the exact fraction beyond whole Euros has problems. At first, the pile size to hand size ratio reached a critical level, which hampers access a lot. Second, since access is hampered a lot (pretty much like reading a really large file from the hard drive with random access), it is not entirely convenient to stand in front of a large waiting queue of other customers, looking for the coins you need, especially if these customers are going from annoyed to angry to violent at rapid pace.
Thus, I needed a solution. I had to be able to give the fraction beyond whole Euros efficiently for every fraction possible. It is easy to see that efficiency raises if the number of coins decreases. Imagine searching for the only 1Ct-coin in a large mountain of 2Ct-coins opposed to searching for the 1Ct-coin in a set of three coins.
But how to compute this set of coins required? I figured that I know an efficient algorithm to break a given amount into the optimal sequence of coins (I guess you know it, too: Add the largest fitting coin to the sequence and subtract its value from the amount. Repeat until amount is zero.). But how to get from this algorithm to a set of coins I need?
I figured: I can take a single coin as often as I like, but there exists an upper bound for this amount of coins with the same value. At a certain point, it must be more efficient to just use another coin instead of this one. Thus, I figured you could just pile up coins with the same value and look if the optimal algorithm is able to create a result with less coins. Once that happens, I crossed the bound and know the optimal amount of coins (one less).
So I calculated: 1 x 1Ct. Algorithm? Algorithm says “1Ct”. 2 x 1Ct. Algorithm? Algorithm says 1 x 2Ct. Ok, so I just need a single 1Ct-coin.
So I calculated more: 1 x 2Ct. Algorithm? Algorithm says: 1 x 2Ct. 2 x 2 Ct. Algorithm? Algorithm says: 2 x 2Ct. 3 x 2 Ct. Algorithm? Algorithm says: 1 x 5Ct, 1 x 1 Ct. Ok, so I need two 2Ct-coins.
Repeat that for all coin values you have and (for Euros) you will end up with: 1 x 1Ct, 2 x 2Ct, 1 x 5Ct, 1 x 10Ct, 2 x 20Ct, 1 x 50 Ct, 1 x 1 Eur, 2 x 2 Eur. This can represent any monetary value up to 5.99Eur and you can get the optimal coin-combination for each value at maximum speed, because you have the minimum amount of coins and the right combination of coins to have the optimal combination of coins for each fraction! Success!
If you are from the dollar-space or from some other space, you will not be able to use my results directly, of course, but you can just execute the algorithm for yourself and look what happens 
Greetings, Tetha.
