4399后端笔试题第三题

题目：给定不同面额的硬币coins和每种硬币的数量counts，以及一个总金额amount

编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1.

示例输入

1 2 5// 硬币面额coins

3 2 1// 每种面额对应的数量counts

11// 总金额amount

示例输出

5

#include <vector>
#include <iostream>
using namespace std;
 
// count为硬币个数
// sum为当前和
int backtracking(int &count, vector<int> coins, int startindex, int sum, int amount) {
    if (startindex == coins.size()) {
        return -1;
    }
    if (sum == amount) {// 当前和满足amount，立即返回
        return sum;
    }
    for (int i = startindex; i < coins.size(); ++i) {
        if (sum + coins[i] > amount)
            continue;
        count++;
        sum += coins[i];
        if (backtracking(count, coins, i + 1, sum, amount) == amount)
            return amount;
        sum -= coins[i];
        count--;
    }
}
 
int main() {
    vector<int> coins = { 1, 2, 5 };
    vector<int> counts = { 3, 2, 1 };
    vector<int> new_coins;// new_coins为整合为一个并且排序好的从大到小的硬币数组
    for (int i = counts.size() - 1; i >= 0; --i) {
        int numbers = counts[i];// 最大硬币的个数
        for (int j = 0; j < numbers; ++j) {
            new_coins.emplace_back(coins[i]);// 将最大的硬币放入数组最前面
        }
    }
 
    int result{};
    backtracking(result, new_coins, 0, 0, 11);
  	if (result == 0) result = -1;
    cout << result << endl;
    return 0;
}

}