change (denominations) calculator

I'm looking for a solution to calculate denominations of change. My problem has the denominations: 50 & 20.

So given the amount: 130, there should be 1x50 + 4x20, and amount: 80, there should be 0x50 + 4x20, etc.

I have tried looking up the 开发者_如何学Gocoin problem but cannot get a decent answer, and when there are more than 2 types on denominations, there seems to be a brick wall for the coin problem (from what I've read).

Is there any complete solution to this? Or preferably a solution to more than 2 denomination types?

I would also like to be able to supply an amount of each available denomination.

Bonus if you can solve in pseedo code

If you have only two denominations the problem becomes:

find x and y such that 
a*x + b*y = c

This can be solved using the Extended Euclidean Algorithm

If you have more than 3 denominations, the most common solution uses uses dynamic programming to "brute force" the possibilities. You can check this similar question

Check the relative but more general question looking-to-understand-the-rationale-for-money-denomination at math.stackexchange.com.

Also making-change-for-a-dollar-and-other-number-partitioning-problems, which nicely explains how generating functions are the solution to the general problem.

If your problem is restricted to two coins, it's far more easier.

here is a code solution: http://www.codeproject.com/KB/recipes/coinChangeProblem.aspx

unfortunately the code is really ugly but should be able to clean up easily

u can use simple "greedy algorithm"

http://en.wikipedia.org/wiki/Greedy_algorithm

Just keep subtracting the biggest denomination you can. IE keep subtracting 50s until whats left is <50, then keep subtracting 20s. This works no matter how many denominations you have.