C++ 算法：用多种面值钱币凑出指定金额的方案数

珅泽教育的小珅同学有 n 种面值不同的钱币，具体地说，小珅有面值 w1 的钱币 c1 个，面值 w2 的钱币 c2 个,...,面值 wn 的钱币 cn 个。

小珅想知道用手中的钱币，恰好凑出 m 的方法有多少种?

输入

第 1 行两个正整数 n, m, 用空格分隔第 2 行 n 个正整数 w1, w2, ⋯, wn 第 3 行 n 个正整数 c1, c2, ⋯, cn

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> w(n);
    vector<int> c(n);

    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    vector<int> dp(m + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = m; j >= w[i]; j--) {
            for (int k = 1; k <= c[i] && k * w[i] <= j; k++) {
                dp[j] += dp[j - k * w[i]];
            }
        }
    }

    cout << dp[m] << endl;

    return 0;
}

代码解释

输入: 代码首先读取输入数据，包括钱币种数 n，目标金额 m，每种钱币的面值 w1, w2, ..., wn 和数量 c1, c2, ..., cn。
动态规划数组: 定义一个大小为 m + 1 的数组 dp，dp[i] 表示用给定的钱币凑出 i 的方案数。初始化 dp[0] 为 1，因为凑出 0 的方案数为 1（即不使用任何钱币）。
循环遍历: 代码使用三个循环来计算 dp 数组。
- 外层循环遍历每种钱币，从第 0 种到第 n - 1 种。
- 中层循环遍历目标金额，从 m 到 w[i]，确保当前钱币的面值小于等于目标金额。
- 内层循环遍历当前钱币的使用数量，从 1 到 c[i]，确保使用的钱币数量不超过当前钱币的可用数量。
状态转移: 在每个循环中，代码计算 dp[j] 的值，表示凑出 j 的方案数。当前方案数等于所有使用 k 个当前钱币凑出 j - k * w[i] 的方案数之和。
输出: 最后，代码输出 dp[m] 的值，表示用给定的钱币凑出 m 的方案数。

算法时间复杂度

算法的时间复杂度为 O(n * m * c)，其中 n 为钱币种数，m 为目标金额，c 为钱币数量的最大值。

总结

这篇文章介绍了一种用 C++ 代码解决经典组合问题的方案，即用多种面值钱币凑出指定金额的方案数问题。通过动态规划算法，代码可以高效地计算出所有可能的方案数，并展示了算法的实现细节和时间复杂度分析。