有什么好的非递归算法来确定是否可以通过一组数字来累加构建通过量？
什么是非递归算法，用于确定是否可以从一组数字中累加构建传入的金额。
以我为例，我正在确定是否可以通过合计一组账单(例如5美元，10美元和20美元)来满足某个货币金额(例如40美元)。这是一个简单的示例，但是该算法需要适用于任何货币集(某些货币使用时髦的账单金额，而某些账单在给定时间可能不可用)。
因此，$ 50可以用一组($ 20和$ 30)来满足，而不能用一组($ 20和$ 40)来满足。非递归要求是由于目标代码库是针对" SQL Server 2000"的，因此对递归的支持受到限制。
另外，这是为了支持多货币环境，在该环境中可用的账单集可能会发生变化(例如，想想一个外币兑换柜员)。
解决方案
回答
编辑：以下将在某些时候工作。考虑一下为什么它不能一直有效，以及如何更改它以覆盖其他情况。
从最大的钞票到最小的钞票开始构建。这将使票据数量最少。
取初始金额，并在不影响价格的情况下，尽可能多地应用最大的账单。
转到下一个最大的帐单，并以相同的方式应用它。
继续这样做，直到账单最小为止。
然后检查总和是否等于目标数量。
回答
我们有两次声明该算法不能递归，但这是该问题的自然解决方案。一种或者另一种方式，我们将需要执行搜索来解决此问题。如果递归不可用，则需要手动回溯。
选择低于目标值的最大货币值。如果匹配，就完成了。如果不是，则将当前目标值压入堆栈，然后从目标值中减去所选择的货币值。继续进行此操作，直到找到匹配项或者没有其他货币值为止。然后使用堆栈回溯并选择其他值。
基本上，这是具有手动管理堆栈的循环内的递归解决方案。
回答
这可以通过称为动态编程的方法来解决。不幸的是，我的讲义太过关注生物信息学，因此我们必须自己搜索。
回答
这听起来像子集和问题，这是已知的NP完全问题。
祝你好运。
编辑：如果我们允许任意数量的某种面额的纸币/硬币(而不是一个)，那么这是一个不同的问题，并且更加容易。看到硬币问题。当阅读另一个(可疑)类似问题的答案时，我意识到了这一点。
回答
如果我们将每个面额都视为以n为底的数字上的一个点，其中n是我们需要的最大纸币数，则可以递增该数字，直到用尽问题空间或者找到解决方案为止。
我们需要的最大纸币数是所需的总数除以最低面额的纸币。
这是对这个问题的蛮力反应，但是肯定会奏效。
这是一些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
回答
我同意Tyler的描述，这是Subset Sum问题的一个变体，被称为NP-Complete。在这种情况下，我们会很幸运，因为我们使用的是一组有限的值，因此我们可以在此处使用动态编程技术来稍微优化问题。就代码的一些一般性想法而言：
- 由于我们处理的是金钱，因此给定的账单只有很多种更改方式，在大多数情况下，某些账单比其他账单使用得更多。因此，如果我们存储结果，则可以保留一组最常见的解决方案，然后在尝试查找实际解决方案之前先对其进行检查。
- 除非我们使用的语言不支持递归，否则没有理由完全忽略解决方案中递归的使用。尽管可以使用迭代来解决任何递归问题，但在这种情况下，递归很可能更容易编写。
其他一些用户(例如Kyle和seanyboy)为我们编写自己的函数指明了正确的方向，因此我们应该看看他们为工作提供了什么。
回答
没有递归和有限递归之间是有区别的。不要混淆两者，因为我们会错过本课的重点。
例如，我们可以使用C ++或者其他低级语言中的递归来安全地编写阶乘函数，因为即使在少数递归中，结果甚至会溢出我们最大数量的容器。因此，我们将要面对的问题是在存储结果之前，由于递归而无法对结果进行处理。
这就是说，无论我们找到什么解决方案，甚至都没有深入了解问题，因为我看到其他人已经做过，我们将必须研究算法的行为，并且可以确定什么是最坏情况下的方案深度堆。
如果平台支持最坏的情况，则无需完全避免递归。
回答
算法：
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，回答：否
回答
我们可以将动态编程方法作为MattW来解决此问题。提及。
给定有限数量的账单和最大金额，我们可以尝试以下解决方案。该代码段位于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]);
输出：
15 : False 50 : False 60 : True 110 : True 120 : True 150 : True 151 : False
