<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number">Algorithm to find which numbers from a list of size n sum to another number</a>  </p>
</blockquote>



<p>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.</p>

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

<p>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?</p>

[{'answer_id': 67026, 'author': 'Todd Gamblin', 'author_id': 9122, 'author_profile': 'https://Stackoverflow.com/users/9122', 'pm_score': 1, 'selected': False, 'text': '<p>You are looking for the coin change problem:</p>\n\n<ul>\n<li><p><a href="http://en.wikipedia.org/wiki/Coin_problem" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Coin_problem</a></p></li>\n<li><p><a href="http://www.egr.unlv.edu/~jjtse/CS477/DP%20Coin%20Change.html" rel="nofollow noreferrer">http://www.egr.unlv.edu/~jjtse/CS477/DP%20Coin%20Change.html</a></p></li>\n<li><p><a href="http://www.algorithmist.com/index.php/Coin_Change" rel="nofollow noreferrer">http://www.algorithmist.com/index.php/Coin_Change</a></p></li>\n</ul>\n'}, {'answer_id': 67028, 'author': 'Jason Cohen', 'author_id': 4926, 'author_profile': 'https://Stackoverflow.com/users/4926', 'pm_score': 0, 'selected': False, 'text': '<p>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.</p>\n'}, {'answer_id': 67062, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 1, 'selected': False, 'text': '<p>This seems closely related to the Subset Sum Problem, which is NP-Complete in general.</p>\n'}, {'answer_id': 67075, 'author': 'Jason Punyon', 'author_id': 6212, 'author_profile': 'https://Stackoverflow.com/users/6212', 'pm_score': 0, 'selected': False, 'text': "<p>Sum = 100<br>\nBills = (40,30,20,10)</p>\n\n<p>Number of 40's = 100 / 40 = 2\nRemainder = 100 % 40 = 20</p>\n\n<p>Number of 30's = 20 / 30 = 0\nRemainder = 20 % 30 = 20</p>\n\n<p>Number of 20's = 20 / 20 = 1\nRemainder = 20 % 20 = 0</p>\n\n<p>As soon as remainder = 0 you can stop.</p>\n\n<p>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)</p>\n"}, {'answer_id': 73643, 'author': 'seanyboy', 'author_id': 1726, 'author_profile': 'https://Stackoverflow.com/users/1726', 'pm_score': 0, 'selected': False, 'text': '<p>You know - You asked this exact same question twice now. </p>\n\n<p><a href="https://stackoverflow.com/questions/64723/what-is-a-good-non-recursive-algorithm-for-deciding-whether-a-passed-in-amount">What is a good non-recursive algorithm for deciding whether a passed in amount can be built additively from a set of numbers?</a></p>\n'}]
['https://Stackoverflow.com/questions/67004', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/8852/']