C++剪枝问题凑钱方案数

Question

题目描述
给出 n 个硬币及其面额（同面额可能有多个），问使用这 n 个硬币，有多少种不同的方案可以凑出 k 块钱。若一种也无法凑出，请输出 −1。

（无视面额是否相同，只要使用了不同的硬币即视为不同方案）

如对于 n=5，硬币：1 2 2 2 3，凑 k=3 块钱，答案应为 4。

输入格式
第一行两个整数
n 和 k，表示硬币数量及目标金额。
第二行
n 个整数，表示每个硬币的面额。
输出格式
输出有多少种不同的方案可以凑出
𝑘
k 块钱。若一种也无法凑出，请输出
−1。

样例
输入数据 1
5 3
1 2 2 2 3
输出数据 1
4

Answer 1

以下内容由AIGC及阿里嘎多学长共同生成、有用望采纳：

---

好的，让我们一步一步来解决这个问题。

1. 理解题目要求

题目要求我们计算使用给定硬币面额凑出特定金额的不同方案数。这里的关键是“不同方案”，意味着即使硬币面额相同，只要它们是不同的硬币，也被视为不同的方案。

2. 输入处理

我们需要读取两个整数（硬币数量和目标金额），然后读取n个整数表示每个硬币的面额。

3. 算法设计

我们可以使用回溯算法来解决这个问题，并在必要时进行剪枝。基本思路是：

• 从第一个硬币开始，考虑是否使用这个硬币。
• 如果使用，递归考虑剩下的硬币和减少的目标金额。
• 如果不使用，继续考虑下一个硬币。
• 在递归过程中，如果目标金额变为负或硬币用完但金额未达到0，则回溯并尝试其他选项。

4. 输出结果

最后，输出凑钱方案的数量。如果无法凑出目标金额，则输出-1。

C++代码实现

#include <iostream>
#include <vector>
using namespace std;

int count = 0; // 全局变量，用于记录方案数

void countWays(vector<int>& coins, int index, int amount, int n) {
    if (amount == 0) {
        count++;
        return;
    }
    if (index == n || amount < 0) {
        return;
    }

    // 选择当前硬币
    countWays(coins, index + 1, amount - coins[index], n);
    // 不选择当前硬币
    countWays(coins, index + 1, amount, n);
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> coins(n);
    for (int i = 0; i < n; i++) {
        cin >> coins[i];
    }

    countWays(coins, 0, k, n);

    if (count == 0) {
        cout << -1 << endl;
    } else {
        cout << count << endl;
    }

    return 0;
}

代码解释

1. 全局变量 count 用于记录不同的凑钱方案数。
2. 函数 countWays 是一个递归函数，用于探索所有可能的凑钱方案。
   • coins 是硬币面额的数组。
   • index 是当前考虑的硬币的索引。
   • amount 是当前需要凑出的金额。
   • n 是硬币的总数。
3. 主函数 main 读取输入数据，并调用 countWays 函数。
4. 输出结果：如果 count 为0，则输出-1，表示无法凑出目标金额；否则输出 count。

这个程序通过递归和剪枝的方式，有效地计算出使用给定硬币面额凑出特定金额的不同方案数。