What is a **non recursive** 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 any currency set (some currencies use funky bill amounts and some bills may not be available at a given time).

So $50 can be met with a set of ($20 and $30), but cannot be met with a set of ($20 and $40). The non-recursive requirement is due to the target code base being for `SQL Server 2000`

where the support of recursion is limited.

In addition this is for supporting a multi currency environment where the set of bills available may change (think a foreign currency exchange teller for example).

相关问题

- Clear And Efficient 3D Range Tree Implementation
- Storing Large Number Of Files in File-System
- What are the shift rules for Boyer–Moore string se
- Problems with DCT and IDCT algorithm in java
- How to determine if a GPS coordinate lies within a

相关文章

- Clear And Efficient 3D Range Tree Implementation
- Storing Large Number Of Files in File-System
- What are the shift rules for Boyer–Moore string se
- Problems with DCT and IDCT algorithm in java
- How to determine if a GPS coordinate lies within a
- What is the algorithm for generating the maze in t
- Topological sort python
- Is “house coloring with three colors” NP?

There's a difference between no recursion and limited recursion. Don't confuse the two as you will have missed the point of your lesson.

For example, you can safely write a factorial function using recursion in C++ or other low level languages because your results will overflow even your biggest number containers within but a few recursions. So the problem you will face will be that of storing the result before it ever gets to blowing your stack due to recursion.

This said, whatever solution you find - and I haven't even bothered understanding your problem deeply as I see that others have already done that - you will have to study the behaviour of your algorithm and you can determine what is the worst case scenario depth of your stack.

You don't need to avoid recursion altogether if the worst case scenario is supported by your platform.

If you treat each denomination as a point on a base-n number, where n is the maximum number of notes you would need, then you can increment through that number until you've exhausted the problem space or found a solution.

The maximum number of notes you would need is the Total you require divided by the lowest denomination note.

It's a brute force response to the problem, but it'll definitely work.

Here's some p-code. I'm probably all over the place with my fence posts, and it's so unoptimized to be ridiculous, but it should work. I think the idea's right anyway.

Algorithm: 1. Sort currency denominations available in descending order.

2. Calculate Remainder = Input % denomination[i] i -> n-1, 0

3. If remainder is 0, the input can be broken down, otherwise it cannot be.

Example:

Input: 50, Available: 10,20

[50 % 20] = 10, [10 % 10] = 0, Ans: Yes Input: 50, Available: 15,20

[50 % 20] = 10, [10 % 15] = 15, Ans: No

You have twice stated that the algorithm cannot be recursive, yet that is the natural solution to this problem. One way or another, you will need to perform a search to solve this problem. If recursion is out, you will need to backtrack manually.

Pick the largest currency value below the target value. If it's match, you're done. If not, push the current target value on a stack and subtract from the target value the picked currency value. Keep doing this until you find a match or there are no more currency values left. Then use the stack to backtrack and pick a different value.

Basically, it's the recursive solution inside a loop with a manually managed stack.

This sounds like the subset sum problem, which is known to be NP-complete.

Good luck with that.

Edit:If you're allowed arbitrary number of bills/coins of some denomination (as opposed to just one), then it's a different problem, and is easier. See the coin problem. I realized this when reading another answer to a (suspiciously) similar question.You can deal with this problem with

Dynamic Programmingmethod as MattW. mentioned.Given limited number of bills and maximum amount of money, you can try the following solution. The code snippet is in C# but I believe you can port it to other language easily.

Output:12 下一页