c++ - 硬币找零问题

Question

假设我有 4 个面额为 1 3 4 5 的硬币。我想把它变成 7。我学习如何找到可以完成的可能方法。但我想确定为此必须使用的最少硬币数量是多少。示例：5+1+1=7 再次 3+4=7。所以硬币的最小数量是2。任何伪代码或解释或源代码都会有所帮助

Answer 1

如果要对数字 n 进行更改，请设置一个数组 number_of_coins[n] 并从左到右填写。number_of_coins[0] 显然是 0。接下来的几个你可以手动完成（尽管一旦你有了算法，它会自动填充它们）。要在数组中填充较大的条目 m，请考虑以下问题：如果我从 m 中删除 1 美分怎么办？还是3美分？还是4美分？还是5美分？

一旦您的硬币数组数量达到 n，您就可以向后遍历它以找到要使用的确切硬币。

Answer 2

我会试一试。我认为您应该定义面额的向量：

vector<int> denominations {1,3,5,7};

从那里，编写一个递归函数，接收面额，以及从面额中赚取的金额：

int recursive_totals(const vector<int> denominations, int amount_to_make);

amount_to_make如果小于或等于 0，此函数将返回 0 ，否则它将遍历面额：

int sum_totals = 0;
for (int denom : denominations)
{
    if (amount_to_make - denom == 0)
        sum_totals+=1;
    else
        sum_totals+=recursive_totals(denominations, amount_to_make - denom);
}

这是粗略的代码，可能需要调整，但我认为递归函数在这里有效。我看到的一个直接问题是顺序与我在这里编写的方式无关，并且您可能会得到重复，但有一种方法可以解决这个问题。

编辑：我让它工作，但不会在这里发布代码。此方法有效，如果您选择尝试，请随时提出您需要的任何问题，我会尽力提供帮助。