Recently I challenged my co-worker to write an algorithm to solve this problem:
Find the least number of coins required that can make any change from 1 to 99 cents. The coins can only be pennies (1), nickels (5), dimes (10), and quarters (25), and you must be able to make every value from 1 to 99 (in 1-cent increments) using those coins.
However, I realized that I don't actually know how to do this myself without examining every possible combination of coins. There has to be a better way of solving this problem, but I don't know what the generic name for this type of algorithm would be called, and I can't figure out a way to simplify it beyond looking at every solution.
I was wondering if anybody could point me in the right direction, or offer up an algorithm that's more efficient.
The answer is 10 coins, 3 Quarters, 1 dime, 2 nickel, and 4 pennies. With this combination you can produce any number between 1-99 cents. An alternative answer would be 6 coins, 3 Quarters, 2 dimes and 1 nickel. In this example you will range most change between 5-95 cents, in 5 cents increments.
So, we create a minCoins array - minCoins[sum+1] where minCoins[i] represents minimum number of coins required to make change for amount = i. We build up the array in bottom up manner starting with minCoins[0]. The time complexity of the Dynamic Programming solution is O(n*sum). The space complexity is O(sum).
11 coins is the fewest. 0.01 + 0.05 + 0.1 + 0.25 = 0.41 we need 59 more pennies so 60 pennies, and 1 nickel, dime, and quarter gives 63 coins being the most.
What you are looking for is Dynamic Programming.
You don't actually have to enumerate all the possible combinations for every possible values, because you can build it on top of previous answers.
You algorithm need to take 2 parameters:
[1, 5, 10, 25]
[1, 99]
And the goal is to compute the minimal set of coins required for this range.
The simplest way is to proceed in a bottom-up fashion:
Range Number of coins (in the minimal set) 1 5 10 25 [1,1] 1 [1,2] 2 [1,3] 3 [1,4] 4 [1,5] 5 [1,5]* 4 1 * two solutions here [1,6] 4 1 [1,9] 4 1 [1,10] 5 1 * experience tells us it's not the most viable one :p [1,10] 4 2 * not so viable either [1,10] 4 1 1 [1,11] 4 1 1 [1,19] 4 1 1 [1,20] 5 1 1 * not viable (in the long run) [1,20] 4 2 1 * not viable (in the long run) [1,20] 4 1 2
It is somewhat easy, at each step we can proceed by adding at most one coin, we just need to know where. This boils down to the fact that the range [x,y]
is included in [x,y+1]
thus the minimal set for [x,y+1]
should include the minimal set for [x,y]
.
As you may have noticed though, sometimes there are indecisions, ie multiple sets have the same number of coins. In this case, it can only be decided later on which one should be discarded.
It should be possible to improve its running time, when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for, I think.
For example, note that:
[1,5] 4*1 1*5 [1,9] 4*1 1*5
we add a nickel to cover [1,5]
but this gives us up to [1,9]
for free!
However, when dealing with outrageous input sets [2,3,5,10,25]
to cover [2,99]
, I am unsure as how to check quickly the range covered by the new set, or it would be actually more efficient.
You can very quickly find an upper bound.
Say, you take three quarters. Then you would only have to fill in the 'gaps' 1-24, 26-49, 51-74, 76-99 with other coins.
Trivially, that would work with 2 dimes, 1 nickel, and 4 pennies.
So, 3 + 4 + 2 + 1 should be an upper bound for your number of coins, Whenever your brute-force algorithm goes above thta, you can instantly stop searching any deeper.
The rest of the search should perform fast enough for any purpose with dynamic programming.
(edit: fixed answer as per Gabe's observation)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With