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).

相关问题

- Find sum of first 1000 prime numbers in python [du
- What is a good non-recursive algorithm for decidin
- Searching for the best fit price for multiple cust
- Count of non-repeating digits
- Algorithm to divide black and white chocolate bar

相关文章

- 数独回溯算法（JAVA）(Sudoku backtracking algorithm (Java))
- 由元件发生删除子列表（计划）(delete sublist by element occurrenc
- 随机快速排序在Java中需要suble解决？(randomized quick sort in Ja
- 在不同的列表C＃匹配的项目(C# Matching items in different lists
- 二进制搜索字符串的树（平衡之前）(Binary Search Tree of Strings (be
- 如何延长二进制搜索迭代器消耗多个目标(How to extend a binary search i
- 较大输入动态规划(Dynamic programming with large inputs)
- 找到一个矩阵的最短路径算法(Algorithm to find the shortest path

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 下一页