硬币找零问题

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，此函数将 return 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);
}

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

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