Counting Change

Page 1 of 1

5 Replies - 32635 Views - Last Post: 28 January 2012 - 07:28 PM

#1 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

Counting Change

Posted 10 January 2012 - 10:29 PM

POPULAR

This is a very easy and standard problem. I chose to post it because I know many people will come up with an inefficient solution for it. The only solution possible seems to be the inefficient brute forcing solution, but actually there's a better way that requires an algorithm design technique called dynamic programming. Mastering dynamic programming can greatly increase your skill and it can reduce the time complexity from being exponential to polynomial. So hopefully you will enjoy learning about dynamic programming by trying out this simple and fun problem.

Problem:

You are given a set of coins, each coin having a certain value, and you have an infinite supply of each type of coin. Now you want to count how many ways you can make change for a certain amount of cents using the coins available.

Example:
lets say the coins available are {1, 5, 10} and you want to make change for 11 cents. There are 4 ways this can be done.
1+10, 5+5+1, 1*11, 5+1*6.

To Do:
Write a program that takes the set of coins and the change amount as input, and output how many possible ways are there to make the change amount using the coins available.

Note: There's only 1 way to make change for 0 cents.

Enjoy.

Is This A Good Question/Topic? 5

Replies To: Counting Change

#2 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

Re: Counting Change

Posted 12 January 2012 - 08:06 PM

Alright looks like I'll get it started since no one has. You can submit any solution you want that solves the problem. Enjoy.

Spoiler

#3 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

Re: Counting Change

Posted 20 January 2012 - 06:26 AM

There is actually no dynamic programming required to write an optimal algorithm. Of course the running time is exponential in the number of coins but so is the number of combinations, so it can hardly be avoided.

This algorithm avoids the subproblems I think you are trying to avoid by dynamic programming by enforcing that the coins you take into account are strictly increasing. It's common technique to not visit any permutations of the same solution in a recursive function.

Spoiler

I think you are confusing this with the famous make change problem which is as follows:

Given a list of coins and and an amount of change, what is the least amount of coins you need to make that amount of change.

Of course the previous algorithm can be used to solve that as well but dynamic programming can in this case provide a significantly more efficient (read polynomial) solution.

Don't be tricked into thinking a greedy algorithm will work. Take a list of coins {1, 7, 10} and to make 14. A greedy algorithm will create {10, 1, 1, 1, 1} while the optimal one is {7, 7}. In all existing coin systems I know of a greedy algorithm will always give an optimal solution.

This post has been edited by Karel-Lodewijk: 20 January 2012 - 06:32 AM

#4 curryjl

Reputation: 4
• Posts: 16
• Joined: 02-March 09

Re: Counting Change

Posted 25 January 2012 - 10:45 AM

I am still working on solving this problem without stealing to much of your code. I am having tough time writing an algorithm to do this... Let me know if this sounds like a good idea. create a sum variable and add each item in the array to it and check if the sum is greater than the change entered by the user. If the item added to the sum would be greater don't add to sum. This will only do one solution though I believe and you are wanting to know how many different ways you can calculate the change amount. I hope this is at least suppose to be somewhat of a difficult program that would make me feel better for failing..

#5 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

Re: Counting Change

Posted 28 January 2012 - 07:08 PM

Karel-Lodewijk, on 20 January 2012 - 04:26 PM, said:

There is actually no dynamic programming required to write an optimal algorithm. Of course the running time is exponential in the number of coins but so is the number of combinations, so it can hardly be avoided.

This algorithm avoids the subproblems I think you are trying to avoid by dynamic programming by enforcing that the coins you take into account are strictly increasing. It's common technique to not visit any permutations of the same solution in a recursive function.

Spoiler

I think you are confusing this with the famous make change problem which is as follows:

Given a list of coins and and an amount of change, what is the least amount of coins you need to make that amount of change.

Of course the previous algorithm can be used to solve that as well but dynamic programming can in this case provide a significantly more efficient (read polynomial) solution.

Don't be tricked into thinking a greedy algorithm will work. Take a list of coins {1, 7, 10} and to make 14. A greedy algorithm will create {10, 1, 1, 1, 1} while the optimal one is {7, 7}. In all existing coin systems I know of a greedy algorithm will always give an optimal solution.

I am aware of the other make change problem you are referring to, dp is the way to go most of the time, unless the coins given are in US denominations, in that case a greedy algorithm will be correct, and faster. However for the problem I posted, dp is the best way to go. The algorithm you are talking about is basically a brute forcing algorithm which has a solution set of non decreasing coin values (so as to not count duplicate solutions). It is correct but not efficient, it will still visit the same subproblems over and over again, thus wasting time. To improve the algorithm's running time, you either memoize, if you want to do top-down, or you can build the solution from the bottom-up (like i did). All in all a dp algorithm for this problem will have a running time of theta(n*m) where n is the number of coins, and m is the value of change. While the approach you are referring to will take exponential time.

This post has been edited by mostyfriedman: 28 January 2012 - 07:29 PM

#6 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

Re: Counting Change

Posted 28 January 2012 - 07:28 PM

curryjl, on 25 January 2012 - 08:45 PM, said:

I am still working on solving this problem without stealing to much of your code. I am having tough time writing an algorithm to do this... Let me know if this sounds like a good idea. create a sum variable and add each item in the array to it and check if the sum is greater than the change entered by the user. If the item added to the sum would be greater don't add to sum. This will only do one solution though I believe and you are wanting to know how many different ways you can calculate the change amount. I hope this is at least suppose to be somewhat of a difficult program that would make me feel better for failing..

I don't quite understand your approach. can you provide an example, use this test case coins = {1, 5, 10}, change = 13