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 countMethods(vector<int>& weights, vector<int>& 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<int> weights(n); vector<int> 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;