What is a good algorithm for deciding whether a passed in amount can be built additively from a set of numbers?

Question

What is a good algorithm for deciding whether a passed in amount can be built additively from a set of numbers. In my case I'm determining whether a certain currency amount (such as $40) can be met by adding up some combination of a set of bills (such as $5, $10 and $20 bills). That is a simple example, but the algorithm needs to work for the generic case where the bill set can differ over time (due to running out of a bill) or due to bill denominations differing by currency. The problem would apply to a foreign exchange teller at an airport.

So $50 can be met with a set of ($20 and $30), but cannot be met with a set of ($20 and $40).

In addition. If the amount cannot be met with the bill denominations available how do you determine the closest amounts above and below which can be met?

Answer 1

You are looking for the coin change problem:

• http://en.wikipedia.org/wiki/Coin_problem

• http://www.egr.unlv.edu/~jjtse/CS477/DP%20Coin%20Change.html

• http://www.algorithmist.com/index.php/Coin_Change

Answer 2

Start with the largest bills and work down. With each denomination, start with the largest number of those bills and work down. You might need fewer of a large denomination because you need multiple smaller ones to hit a value on the head.

Answer 3

This seems closely related to the Subset Sum Problem, which is NP-Complete in general.

Answer 4

Sum = 100
Bills = (40,30,20,10)

Number of 40's = 100 / 40 = 2 Remainder = 100 % 40 = 20

Number of 30's = 20 / 30 = 0 Remainder = 20 % 30 = 20

Number of 20's = 20 / 20 = 1 Remainder = 20 % 20 = 0

As soon as remainder = 0 you can stop.

If you run out of bills then you can't make it up and need to go to the second part which is how close can you get. This is a minimization problem that can be solved with Linear algebra methods (I'm a little rusty on that)

Answer 5

You know - You asked this exact same question twice now.

http://stackoverflow.com/questions/64723/what-is-a-good-non-recursive-algorithm-for-deciding-whether-a-passed-in-amount

Answer 6

A very similar answer has been given here: http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number