----------------------------------- klopyrev Tue Apr 10, 2007 1:11 am Coin Change ----------------------------------- 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 Tue Apr 10, 2007 10:47 am Re: Coin Change ----------------------------------- 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 Tue Apr 10, 2007 11:07 am RE:Coin Change ----------------------------------- 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 Tue Apr 10, 2007 11:09 am RE:Coin Change ----------------------------------- 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 Tue Apr 10, 2007 11:16 am RE:Coin Change ----------------------------------- The method you just described is the greedy method, which does not work in all circumstances as proven above :? ----------------------------------- haskell Tue Apr 10, 2007 11:36 am RE:Coin Change ----------------------------------- Using 5c, 4c, 1c. 8c as the goal. 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 Tue Apr 10, 2007 11:57 am Re: Coin Change ----------------------------------- 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 Tue Apr 10, 2007 11:59 am Re: Coin Change ----------------------------------- 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 Tue Apr 10, 2007 12:02 pm Re: RE:Coin Change ----------------------------------- Using 5c, 4c, 1c. 8c as the goal. 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 Tue Apr 10, 2007 12:11 pm Re: Coin Change ----------------------------------- to prove the greedy algorithm works, verify for all values k