时间戳

首页 > 解决方案 > 将低效的递归硬币找零函数转换为迭代

c++ - 将低效的递归硬币找零函数转换为迭代

问题描述

我有一个低效的递归硬币找零函数，可以计算出给定数量的硬币组合数量。如果可能，我想将其转换为更有效的迭代函数。

一个问题是我正在使用回溯来尝试一个称为面额的数组中的不同硬币。我也在使用记忆，但当数量很大时它不会加快速度。

这是我的代码：

unsigned long long CalculateCombinations(std::vector<double> &denominations, std::vector<double> change,
    double amount, unsigned int index)
{
    double current = 0.0;
    unsigned long long combinations = 0;

    if (amount == 0.0)
    {
        if (change.size() % 2 == 0)
        {
            combinations = Calculate(change);
        }
        return combinations;
    }

    // If amount is less than 0 then no solution exists
    if (amount < 0.0)
        return 0;

    // If there are no coins and index is greater than 0, then no solution exist
    if (index >= denominations.size())
        return 0;

    std::string str = std::to_string(amount) + "-" + std::to_string(index) + "-" + std::to_string(change.size());

    auto it = Memo.find(str);

    if (it != Memo.end())
    {
        return it->second;
    }

    while (current <= amount)
    {
        double remainder = amount - current;
        combinations += CalculateCombinations(denominations, change, remainder, index + 1);
        current += denominations[index];
        change.push_back(denominations[index]);
    }

    Memo[str] = combinations;
    return combinations;
}

任何想法如何做到这一点？我知道硬币找零问题有 DP 解决方案，但我的解决方案并不容易解决。我可以有半便士。

*更新：我将函数更改为迭代，并按比例放大了 2 倍以使用整数，但没有太大区别。

这是我的新代码：

unsigned long long CalculateCombinations(std::vector<int> &denominations, std::vector<int> change, int amount, unsigned int index)
{
    unsigned long long combinations = 0;

    if (amount <= 0)
        return combinations;

    std::stack<Param> mystack;
    mystack.push({ change, amount, index });

    while (!mystack.empty())
    {
        int current = 0;
        std::vector<int> current_coins = mystack.top().Coins;
        int current_amount = mystack.top().Amount;
        unsigned int current_index = mystack.top().Index;
        mystack.pop();

        if (current_amount == 0)
        {
            if (current_coins.size() % 2 == 0)
            {
                combinations += Calculate(std::move(current_coins));
            }
        }
        else
        {
            std::string str = std::to_string(current_amount) + "-" + std::to_string(current_index);
            if (Memo.find(str) == Memo.end())
            {
                // If amount is less than 0 then no solution exists
                if (current_amount >= 0 && current_index < denominations.size())
                {
                    while (current <= current_amount)
                    {
                        int remainder = current_amount - current;
                        mystack.push({ current_coins, remainder, current_index + 1 });
                        current += denominations[current_index];
                        current_coins.push_back(denominations[current_index]);
                    }
                }
                else
                {
                    Memo.insert(str);
                }
            }
        }
    }

    return combinations;
}

备忘录被定义为 std::unordered_set。

DP能解决这个问题吗？问题是我对所有组合都不感兴趣——只对大小均匀的组合感兴趣。

标签： c++recursioncoin-change

解决方案

我在您的代码中没有看到任何丢弃面额的策略。

我的递归答案将是在每个递归阶段创建 2 个孩子：
1 个孩子使用完整的面额列表，并花费 1 个最终面额
第二个孩子丢弃相同的面额

他们每个人都递归，但在第二种情况下，孩子们可以使用的教派少了一个。

我相信返回的结果都是不同的，但当然你会遇到痛苦的情况，即你递归 10000 个级别以获得 100 美元的便士。当您降至 1 面额时，这可以很容易地进行优化，并且可能表明最好在每一轮中处理和丢弃较高面额而不是较低面额。

您还可以检测到所有剩余面额都是彼此的简单倍数的情况，并在不进行完全递归的情况下快速生成排列：生成最小硬币集（每个高面额的最大值），然后用较小的硬币数量反向替换每个硬币.

推荐阅读