What is a good non-recursive algorithm for decidin

2019-10-09 21:56发布

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

2楼-- · 2019-10-09 22:21

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.

3楼-- · 2019-10-09 22:29

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]

    iTotal = 0 
    for iAdd = 1 to Bumplist.size
        iTotal = iTotal + bumplist [iAdd] * Denominations[iAdd]
    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
until (finished)

exit false    
Deceive 欺骗
4楼-- · 2019-10-09 22:33

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.

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

5楼-- · 2019-10-09 22:36

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.

6楼-- · 2019-10-09 22:41

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.

7楼-- · 2019-10-09 22:43

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]);


15 : False
50 : False
60 : True
110 : True
120 : True
150 : True
151 : False
登录 后发表回答