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).
什么是非递归算法,用于决定是否可以从一组数字中相加地构建传入的数量。在我的情况下,我通过将一组账单(例如5美元,10美元和20美元的账单)相加来确定是否可以满足某种货币金额(例如40美元)。这是一个简单的例子,但算法需要适用于任何货币集(某些货币使用时髦的账单金额,某些账单可能在给定时间不可用)。所以50美元可以满足一套(20美元和30美元),但不能满足一套(20美元和40美元)。非递归要求是由于目标代码库是针对SQL Server 2000的,其中递归的支持是有限的。此外,这是为了支持多种货币环境,其中可用的账单可能会发生变化(例如,考虑外币兑换柜员)。
9 个解决方案
#1
3
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.
基本上,它是带有手动管理堆栈的循环内的递归解决方案。
#2
3
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.
如果您将每个面额视为基数n上的一个点,其中n是您需要的最大注释数,那么您可以增加该数字,直到您用尽问题空间或找到解决方案。
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.
这是一些p代码。我可能在我的栅栏上到处都是这个地方,而且它太荒谬了,但它应该可行。无论如何,我认为这个想法是正确的。
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
#3
2
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.
这是一个可以通过称为动态编程的方法解决的问题。不幸的是,我的课程注意到我过于专注于生物信息学,所以你必须自己去谷歌。
#4
2
This sounds like the subset sum problem, which is known to be NP-complete.
这听起来像子集和问题,已知是NP完全的。
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.
编辑:如果您允许任意数量的某些面额的钞票/硬币(而不是一个),那么这是一个不同的问题,并且更容易。看到硬币问题。我在阅读(可疑的)类似问题的另一个答案时意识到了这一点。
#5
1
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:
我同意Tyler - 你所描述的是Subset Sum问题的一个变种,它被称为NP-Complete。在这种情况下,当您使用一组有限的值时,您会有点幸运,因此您可以使用动态编程技术来优化问题。就代码的一些一般想法而言:
- 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.
其他一些用户如Kyle和seanyboy指出了正确的方向来编写自己的功能,所以你应该看看他们为你正在做什么提供了什么。
#6
1
You can deal with this problem with Dynamic Programming method as MattW. mentioned.
您可以使用动态编程方法将此问题作为MattW来处理。提及。
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.
鉴于账单数量有限且金额最大,您可以尝试以下解决方案。代码片段在C#中,但我相信您可以轻松地将其移植到其他语言。
// 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
#7
0
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.
例如,您可以使用C ++或其他低级语言中的递归安全地编写阶乘函数,因为即使是最大数量的容器,您的结果也会溢出,但会有一些递归。因此,您将面临的问题是在结果因为递归而将结果存储到堆栈之前。
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.
如果您的平台支持最坏的情况,则无需完全避免递归。
#8
-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.
然后检查总和是否等于目标金额。
#9
-1
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
算法:1。按降序对货币面额进行排序。 2.计算余数=输入%面额[i] i - > n-1,0 3.如果余数为0,则可以分解输入,否则不能。示例:输入:50,可用:10,20 [50%20] = 10,[10%10] = 0,答案:是输入:50,可用:15,20 [50%20] = 10,[10% 15] = 15,答案:不
#1
3
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.
基本上,它是带有手动管理堆栈的循环内的递归解决方案。
#2
3
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.
如果您将每个面额视为基数n上的一个点,其中n是您需要的最大注释数,那么您可以增加该数字,直到您用尽问题空间或找到解决方案。
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.
这是一些p代码。我可能在我的栅栏上到处都是这个地方,而且它太荒谬了,但它应该可行。无论如何,我认为这个想法是正确的。
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
#3
2
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.
这是一个可以通过称为动态编程的方法解决的问题。不幸的是,我的课程注意到我过于专注于生物信息学,所以你必须自己去谷歌。
#4
2
This sounds like the subset sum problem, which is known to be NP-complete.
这听起来像子集和问题,已知是NP完全的。
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.
编辑:如果您允许任意数量的某些面额的钞票/硬币(而不是一个),那么这是一个不同的问题,并且更容易。看到硬币问题。我在阅读(可疑的)类似问题的另一个答案时意识到了这一点。
#5
1
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:
我同意Tyler - 你所描述的是Subset Sum问题的一个变种,它被称为NP-Complete。在这种情况下,当您使用一组有限的值时,您会有点幸运,因此您可以使用动态编程技术来优化问题。就代码的一些一般想法而言:
- 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.
其他一些用户如Kyle和seanyboy指出了正确的方向来编写自己的功能,所以你应该看看他们为你正在做什么提供了什么。
#6
1
You can deal with this problem with Dynamic Programming method as MattW. mentioned.
您可以使用动态编程方法将此问题作为MattW来处理。提及。
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.
鉴于账单数量有限且金额最大,您可以尝试以下解决方案。代码片段在C#中,但我相信您可以轻松地将其移植到其他语言。
// 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
#7
0
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.
例如,您可以使用C ++或其他低级语言中的递归安全地编写阶乘函数,因为即使是最大数量的容器,您的结果也会溢出,但会有一些递归。因此,您将面临的问题是在结果因为递归而将结果存储到堆栈之前。
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.
如果您的平台支持最坏的情况,则无需完全避免递归。
#8
-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.
然后检查总和是否等于目标金额。
#9
-1
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
算法:1。按降序对货币面额进行排序。 2.计算余数=输入%面额[i] i - > n-1,0 3.如果余数为0,则可以分解输入,否则不能。示例:输入:50,可用:10,20 [50%20] = 10,[10%10] = 0,答案:是输入:50,可用:15,20 [50%20] = 10,[10% 15] = 15,答案:不