2

问题在于最小化提供准确找零所需的硬币数量。总会有 1 的硬币可用，因此问题总会有解决方案。

一些样品硬币套及其解决方案的金额为 40 美分：

硬币组 = {1, 5, 10, 20, 25}，解决方案 = {0, 0, 0, 2, 0}

硬币集 = {1, 5, 10, 20}，解决方案 = {0, 0, 0, 2}

实现返回正确的最小值。硬币的数量，但我无法保存正确的解决方案数组。

int change(int amount, int n, const int* coins, int* solution) {
    if(amount > 0) {
        int numCoinsMin = numeric_limits<int>::max();
        int numCoins;
        int imin;
        for(int i = 0; i != n; ++i) {
            if(amount >= coins[i]) {
                numCoins =  change(amount - coins[i], n, coins, solution) + 1;
                if(numCoins < numCoinsMin) {
                    numCoinsMin = numCoins;
                    imin = i;
                }   
            }   
        }   
        solution[imin] += 1;
        return numCoinsMin;
    }   
    return 0;
}

样品运行：

int main() {
    const int n = 4;
    int coins[n] = {1, 5, 10, 20, 25};
    int solution[n] = {0, 0, 0, 0, 0};
    int amount = 40;

    int min = change(amount, n, coins, solution);
    cout << "Min: " << min << endl;
    print(coins, coins+n); // 1, 5, 10, 20
    print(solution, solution+n); // 231479, 20857, 4296, 199
    return 0;
}
4

1 回答 1

0

您仍然可以使用数组来执行此操作，但我会更改程序的结构以使其递归更简洁。

我将不得不为你编写这个伪代码，因为我几乎不使用 C++，但你可以把它放在一起。这利用了模除法（C# 中的 %，不知道如果它在 C++ 中相同，你可以查一下），它只返回除法的余数。大多数编程语言中的正常除法 (/) 将返回整数答案并忽略任何余数。

//declare a function that takes in your change amount and the length of your coins array
int changeCounter(int amount, int coins.length)
      int index = coins.length-1;

      //check to see if we're done... again dunno what 'or' is in C++, I put ||

      if (amount <= 0 || index < 0)
         **return** your results array or whatever you want to do here

      //sees how many of the biggest coin there are and puts that number in the results
      if amount > coins[index]
      {
        result[index]= (amount / coins[index])
        //now recurse with the left over coins and drop to the next biggest coin
        changeCounter((amount % coins[index]), index-1)
      }

      //if the amount isnt greater than the coin size then there obviously arent any of that size, so just drop coin sizes and recurse again
      else
         changeCounter(amount,index-1)

这应该让您朝着正确的方向开始，我试图为您评论它，很抱歉我不能为您提供完美的 C++ 语法，但将我在这里所做的转换成您正在尝试的应该不会太难去做。

如果您有任何问题，请告诉我

于 2012-11-02T16:53:37.657 回答