-4

什么是一种非递归算法，用于确定是否可以从一组数字中加法构建传入的数量。
就我而言，我正在确定是否可以通过将一组钞票（例如 5 美元、10 美元和 20 美元钞票）的某种组合相加来满足某个货币金额（例如 40 美元）。这是一个简单的例子，但算法需要适用于任何货币集（一些货币使用时髦的账单金额，而一些账单可能在给定时间不可用）。
所以 50 美元可以用一组（20 美元和 30 美元）来满足，但不能用一组（20 美元和 40 美元）来满足。非递归要求是由于目标代码库用于SQL Server 2000递归支持有限的地方。
此外，这是为了支持多币种环境，其中可用的账单集可能会发生变化（例如外币兑换柜员）。

4

9 回答 9

3

您曾两次表示该算法不能递归，但这是该问题的自然解决方案。一种或另一种方式，您将需要执行搜索来解决此问题。如果递归结束，您将需要手动回溯。

选择低于目标值的最大货币值。如果匹配，你就完成了。如果不是，则将当前目标值压入堆栈并从目标值中减去选取的货币值。继续这样做，直到您找到匹配项或没有更多的货币价值。然后使用堆栈回溯并选择不同的值。

基本上，它是带有手动管理堆栈的循环内的递归解决方案。

于 2008-09-15T17:09:08.167 回答
3

如果您将每个面额视为以 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
于 2008-09-15T17:22:09.790 回答
2

这是一个可以通过称为动态规划的方法来解决的问题。不幸的是，我的讲义太专注于生物信息学，所以你必须自己去谷歌搜索。

于 2008-09-15T17:09:59.587 回答
2

这听起来像子集和问题，已知是 NP-complete。

祝你好运。

编辑：如果您允许任意数量的某种面额的钞票/硬币（而不是一个），那么这是一个不同的问题，并且更容易。看硬币问题。在阅读（可疑）类似问题的另一个答案时，我意识到了这一点。

于 2008-09-15T17:15:48.433 回答
1

您可以使用像 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
于 2009-01-01T19:25:34.577 回答
1

我同意Tyler的观点- 你所描述的是Subset Sum问题的一个变体，它被称为NP-Complete。在这种情况下，您有点幸运，因为您使用的是一组有限的值，因此您可以在此处使用动态编程技术来稍微优化问题。就代码的一些一般想法而言：

  • 由于您正在处理金钱，因此只有这么多方法可以使用给定的账单进行更改，并且在大多数情况下，某些账单的使用频率高于其他账单。因此，如果您存储结果，您可以保留一组最常见的解决方案，然后在尝试找到实际解决方案之前检查它们。
  • 除非您使用的语言不支持递归，否则没有理由完全忽略解决方案中递归的使用。虽然任何递归问题都可以使用迭代来解决，但在这种情况下，递归可能更容易编写。

其他一些用户，例如Kyle和seanyboy，为您指明了编写自己的函数的正确方向，因此您应该看看他们为您的工作提供了什么。

于 2008-09-15T17:51:50.967 回答
0

无递归和有限递归是有区别的。不要混淆这两者，因为你会错过课程的重点。

例如，您可以安全地使用 C++ 或其他低级语言中的递归来编写阶乘函数，因为您的结果将溢出即使是您的最大数量的容器，但只有几个递归。因此，您将面临的问题将是在结果由于递归而炸毁您的堆栈之前存储结果。

这就是说，无论你找到什么解决方案——我什至没有费心去深入理解你的问题，因为我看到其他人已经这样做了——你必须研究你的算法的行为，你可以确定最坏情况的深度你的堆栈。

如果您的平台支持最坏的情况，您不需要完全避免递归。

于 2009-01-01T18:43:08.720 回答
-1

算法： 1. 按降序排列可用的货币面额。
2. 计算余数 = Input % denomination[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，答案：否

于 2009-01-01T18:55:16.760 回答
-1

编辑：以下内容有时会起作用。想想为什么它不能一直工作，以及如何改变它以涵盖其他情况。

从最大的账单开始构建它。这将产生最少数量的票据。

在不超过价格的情况下，尽可能多地使用初始金额并应用最大的账单。

转到下一个最大的账单并以相同的方式应用它。

继续这样做，直到你拿到最小的账单。

然后检查总和是否等于目标金额。

于 2008-09-15T17:07:57.780 回答