题目描述珅泽教育的小珅同学有n种面值不同的钱币具体地说小珅有面值w1的钱币c1个面值w2的钱币c2个面值wn的钱币cn个小珅想知道用手中的钱币恰好凑出m的方法有多少种输入第1行两个正整数nm用空格分隔第2行n个正整数w1w2⋯wn第3行n个正整数c1c2⋯cn深搜c++代码

#include #include using namespace std;

int countMethods(vector& weights, vector& counts, int target, int index) { if (target == 0) { return 1; // 目标值为0，找到一种方法 } if (target < 0 || index >= weights.size()) { return 0; // 目标值为负数或已遍历完所有的钱币面值，无法凑出目标值 } int count = 0; for (int i = 0; i <= counts[index]; i++) { count += countMethods(weights, counts, target - i * weights[index], index + 1); // 递归调用，减去当前面值的钱币 } return count; }

int main() { int n, m; cin >> n >> m; vector weights(n); vector counts(n); for (int i = 0; i < n; i++) { cin >> weights[i]; } for (int i = 0; i < n; i++) { cin >> counts[i]; } int answer = countMethods(weights, counts, m, 0); cout << answer << endl; return 0;