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

Question

Possible Duplicate:
Algorithm to find which numbers from a list of size n sum to another number

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 am 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?

score 1 · Answer 1 · answered Sep 15 '08 at 21:12

1

You are looking for the coin change problem:

answered Sep 15 '08 at 21:12

Todd Gamblin

58,354
15
89
96

score 1 · Answer 2 · answered Sep 15 '08 at 21:18

1

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

answered Sep 15 '08 at 21:18

score 0 · Answer 3 · answered Sep 15 '08 at 21:13

0

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.

answered Sep 15 '08 at 21:13

Jason Cohen

81,399
26
107
114

score 0 · Answer 4 · answered Sep 15 '08 at 21:19

0

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)

answered Sep 15 '08 at 21:19

Restore the Data Dumps

38,967
12
96
122

The algorithm as stated does not work for a case such as sum = 60 bills =(40,30). – Stimy Sep 15 '08 at 21:32
Good catch, That'll show me for trying to write code without properly testing. :) – Restore the Data Dumps Sep 17 '08 at 15:55

score 0 · Answer 5 · edited May 23 '17 at 12:08

0

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

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

edited May 23 '17 at 12:08

Community

1
1

answered Sep 16 '08 at 15:33

seanyboy

5,623
7
43
56

It's not the exact same question. The previous question asked for a non-recursive algorithm for which no good answer was provided. This question removed the non-recursive constraint in order to, hopefully, get some better answers. – Stimy Sep 16 '08 at 18:03

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

5 Answers5