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.