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

Question

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

Answer 1

Edit: The following will work some of the time. Think about why it won't work all the time and how you might change it to cover other cases.

Build it starting with the largest bill towards the smallest. This will yeild the lowest number of bills.

Take the initial amount and apply the largest bill as many times as you can without going over the price.

Step to the next largest bill and apply it the same way.

Keep doing this until you are on your smallest bill.

Then check if the sum equals the target amount.

Answer 2

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.

Answer 3

That's a problem that can be solved by an approach known as dynamic programming. The lecture notes I have are too focused on bioinformatics, unfortunately, so you'll have to google for it yourself.

Answer 4

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.

Answer 5

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.

Denominations = [10,20,50,100]
Required = 570

Denominations = sort(Denominations)
iBase = integer (Required / Denominations[1])

BumpList = array [Denominations.count]
BumpList.Clear

repeat 
    iTotal = 0 
    for iAdd = 1 to Bumplist.size
        iTotal = iTotal + bumplist [iAdd] * Denominations[iAdd]
    loop
    if iTotal = Required then exit true

    //this bit should be like a mileometer. 
    //We add 1 to each wheel, and trip over to the next wheel when it gets to iBase
    finished = true
    for iPos from bumplist.last to bumplist.first 
        if bumplist[iPos] = (iBase-1) then bumplist[iPos] = 0 
        else begin
            finished = false
            bumplist[iPos] = bumplist[iPos]+1
            exit for
        end
     loop 
until (finished)

exit false

Answer 6

I agree with Tyler - what you are describing is a variant of the Subset Sum problem which is known to be NP-Complete. In this case you are a bit lucky as you are working with a limited set of values so you can use dynamic programming techniques here to optimize the problem a bit. In terms of some general ideas for the code:

• Since you are dealing with money, there are only so many ways to make change with a given bill and in most cases some bills are used more often than others. So if you store the results you can keep a set of the most common solutions and then just check them before you try and find the actual solution.
• Unless the language you are working with doesn't support recursion there is no reason to completely ignore the use of recursion in the solution. While any recursive problem can be solved using iteration, this is a case where recursion is likely going to be easier to write.

Some of the other users such as Kyle and seanyboy point you in the right direction for writing your own function so you should take a look at what they have provided for what you are working on.

Answer 7

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.

Answer 8

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

Kind regards,

Answer 9

You can deal with this problem with Dynamic Programming method 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.

        // Set of bills
        int[] unit = { 40,20,70};

        // Max amount of money
        int max = 100000;

        bool[] bucket = new bool[max];

        foreach (int t in unit)
            bucket[t] = true;

        for (int i = 0; i < bucket.Length; i++)
            if (bucket[i])
                foreach (int t in unit)
                    if(i + t < bucket.Length)
                        bucket[i + t] = true;

        // Check if the following amount of money
        // can be built additively
        Console.WriteLine("15 : " + bucket[15]);
        Console.WriteLine("50 : " + bucket[50]);
        Console.WriteLine("60 : " + bucket[60]);
        Console.WriteLine("110 : " + bucket[110]);
        Console.WriteLine("120 : " + bucket[120]);
        Console.WriteLine("150 : " + bucket[150]);
        Console.WriteLine("151 : " + bucket[151]);

Output:

15 : False
50 : False
60 : True
110 : True
120 : True
150 : True
151 : False