Coin Change

[klopyrev]

All of you probably know or have heard of the Coin Problem. Basically, the problem is: given several denominations of coins, find the minimum number of coins to make a certain amount. For example, given that you have coins of 1c, 5c and 10c, what is the minimum number of coins needed to make 8c? That would be 4 coins - 5+1+1+1. We are all used to solving this problem greedily. Basically we take as many of the largest coin possible, until we get our amount. So, if we have 8c, we take 1 5. That leaves us with 3c. Then, we take the 1c coin 3 times. Unfortunately, this doesn't always work. If we have coins of 1c, 4c and 5c and we want to make 8c, the greedy solution would tell us that 5+1+1+1 is the best solution, while 4+4 is clearly better. To solve the problem in general, one can use dynamic programming. Unfortunately, dynamic programming is not so easy to code and sometimes, we don't really want to know what is the minimum number of coins needed to make an amount. Sometimes, all we want to know is: will a greedy solution work on a certain set of coin denominations. Would it work with 1c, 5c and 10c coins? The answer is YES. Would it work with 1c, 4c and 5c? NO. The fact that for 8c, it doesn't give the correct answer is a counter example. I have searched for a way to check this for a while now. The only way I could find is to code both a greedy solution and a dynamic programming solution, and check for counter examples. Unfortunately, such code may not always work in time in a contest situation. Does anyone happen to know some mathematical way of verifying whether a given set of coins works? If you do, I would be happy if you share it.

KL

[Hikaru79]

klopyrev @ Tue Apr 10, 2007 2:11 am wrote:

Unfortunately, such code may not always work in time in a contest situation. Does anyone happen to know some mathematical way of verifying whether a given set of coins works? If you do, I would be happy if you share it.

Think linear independence The greedy algorithm will work if the entire set of coins has every larger coin expressible as some integer linear combination of smaller-valued coins. For example, in the real Canadian money system,
1 cent
1 nickel = 5 cents
1 dime = 2 nickels = 10 cents
1 quarter = 2 dimes + 1 nickel = 5 nickels = 25 cents
1 dollar = 4 quarters = 10 dimes = 20 nickels = 100 cents

so greedy algorithm must work since each time you use a larger coin you are objectively better than using its corresponding linear combination as smaller coins. Put differently, the matrix of the values of the coins over the integers should have rank 1.

If you have a set of coins, like in your example, that have linearly INDEPENDENT elements, the greedy algorithm does not work.
5 cents =/= x number of 4-cent coins, where x is an integer

so you run into problems.

Basically, on a contest, examine whether the values of the coins are all multiples of each other. If they are, go greedy!

[md]

Or... there is the brute-force method.

Start with your 1c, 4c, and 5c peices. Figure out the minimum starting from 5c (which should be 4). Save teh answer. Next, figure out the min assuming 4c is the highest (2). Since the answer is smaller then the previous one replace the old one. Then check again with 1c, though we know it'll be larger. You could stop checking 1s after you got to 2 for a performance increase.

[haskell]

There is also the approach of using the coin closest to the amount and finding how many times the coin goes into it. Then using the remainder and doing it over and over until you have it solved.

For example, you are given:

1 c
6 c
27 c

You need to find the best way to get $3.50.

$3.50 / 27c = 12 r 26
26c / 6c = 4 r 2
2c / 1c = 2

Meaning you have 12 27 c coins, 4 6 c coins and 2 1 c coins.

This method can be used for any of these coin problems, and its basically just basic operators and a loop.

[Clayton]

The method you just described is the greedy method, which does not work in all circumstances as proven above

[haskell]

Using 5c, 4c, 1c.

8c as the goal.

code:

if ((given_val / medium_coin) < (given_val / high_coin) && given_val % medium_coin == 0) {     num_of_coin = given_val / medium_coin; } else {     // Greedy method!! }

So, even if we use 20 cents, since 20 / 4 = 5 and 20 / 5 = 4, it will use the proper coin.

The only issue is when it comes to if the lowest coin isn't 1. But this can easily be solved by just testing it the same way the medium coin is tested.

Also, if there are more than 3 coins, you can expand it to encompass all of those coins as well.

Only problem is, it could result in lots of code if there are a lot of coins.

[bugzpodder]

Hikaru79 @ Tue Apr 10, 2007 10:47 am wrote:

klopyrev @ Tue Apr 10, 2007 2:11 am wrote:

Unfortunately, such code may not always work in time in a contest situation. Does anyone happen to know some mathematical way of verifying whether a given set of coins works? If you do, I would be happy if you share it.

Think linear independence The greedy algorithm will work if the entire set of coins has every larger coin expressible as some integer linear combination of smaller-valued coins. For example, in the real Canadian money system,
1 cent
1 nickel = 5 cents
1 dime = 2 nickels = 10 cents
1 quarter = 2 dimes + 1 nickel = 5 nickels = 25 cents
1 dollar = 4 quarters = 10 dimes = 20 nickels = 100 cents

so greedy algorithm must work since each time you use a larger coin you are objectively better than using its corresponding linear combination as smaller coins. Put differently, the matrix of the values of the coins over the integers should have rank 1.

If you have a set of coins, like in your example, that have linearly INDEPENDENT elements, the greedy algorithm does not work.
5 cents =/= x number of 4-cent coins, where x is an integer

so you run into problems.

Basically, on a contest, examine whether the values of the coins are all multiples of each other. If they are, go greedy!

makes no sense. every coin of value n can be expressed as n pennies.

[bugzpodder]

klopyrev @ Tue Apr 10, 2007 1:11 am wrote:

All of you probably know or have heard of the Coin Problem. Basically, the problem is: given several denominations of coins, find the minimum number of coins to make a certain amount. blah blah blah...

coin change is easiest DP algorithm there is. if you cant code coin change in 5 minutes, you don't know DP.

[bugzpodder]

haskell @ Tue Apr 10, 2007 11:36 am wrote:

Using 5c, 4c, 1c.

8c as the goal.

code:

if ((given_val / medium_coin) < (given_val / high_coin) && given_val % medium_coin == 0) {     num_of_coin = given_val / medium_coin; } else {     // Greedy method!! }

this is absurd
given_val/medium_coin will ALWAYS BE >= given_val / high_coin, with equality only if we are using integer division.

[bugzpodder]

to prove the greedy algorithm works, verify for all values k <=n, GREEDY(k) is the best result, for some unspecified value of n.
I think you can prove for n=2d, where d is the largest coin. as for mathematics, i doubt theres a general way of proving this. of a problem expects dp, you wont get away with doing a few cases with greedy anyways.

[klopyrev]

Thanks to everyone. Hikaru: your method doesn't work. In the case of 1, 4 and 5. 5 = 4+1, 4 = 4x1, 1 = 1. I don't see linear independance and I know that the greedy method doesn't work. md, you gave me something like the dynamic programming method. haskell, you gave the greedy method. And bugz, you just emphasized that it can be solved with dynamic programming. I can code it in 5 minutes. It's just a loop like:

code:

for every value from 0 to N       for every denomination of coin A              minimum[n] = min(minimum[n-A]+1)

Thanks for your suggestions, but I've yet to hear a mathematical way. bugz, just because a dp solution can be coded quickly, doesn't always mean that it will run in time. What if you have coins like 1, 400000, 500000? You would have to go up to 800000 to find out it doesn't work, which is not an alternative in some cases.

KL

[bugzpodder]

integer knapsack is np-complete. there is no known polynomial algorithm for it. If you can find one however, I know someone who would give you a million bucks for it.

[bugzpodder]

you are looking for this I presume?
http://citeseer.ist.psu.edu/pearson94polynomialtime.html

[rdrake]

If you want to determine how much change a person gets, clever (ab)use of the modulus operator gets the job done quickly and easily.

I do believe I used the above method for a class assignment.

[klopyrev]

Wow, thanks!!! (To bugz)