c++ - 穷举搜索 : minimum number of coins for change. 使用递归时保留解决方案数组

Question

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

40 美分的一些 sample 硬币套装及其解决方案:

硬币组 = {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;
}

Answer 1

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

我将不得不为您编写伪代码，因为我几乎不使用 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++ 语法中，但将我在这里所做的翻译成你应该不难正在尝试做。

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