用c++完成考虑著名找零问题的一般情形:需找零金额为n,最少要用多少面值为d1<d2<…<dm的硬币?
时间: 2023-09-30 12:06:03 浏览: 133
c语言求硬币找零钱问题
5星 · 资源好评率100%
这个问题可以使用动态规划来解决。我们可以定义一个一维数组 `dp`,其中 `dp[i]` 表示找零金额为 `i` 时所需要的最少硬币数。
初始状态为 `dp[0] = 0`,即找零金额为 0 时不需要硬币。
对于每个 `i`,我们可以枚举所有硬币面值 `di`,这里需要保证 `di <= i`,并更新状态转移方程:
```
dp[i] = min(dp[i], dp[i - di] + 1)
```
其中 `dp[i - di]` 表示找零金额为 `i - di` 时所需要的最少硬币数,加上 1 表示使用一枚面值为 `di` 的硬币。
最终答案为 `dp[n]`。
下面是 C++ 实现代码:
```cpp
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> dp(n + 1, numeric_limits<int>::max());
dp[0] = 0;
vector<int> coins(m);
for (int i = 0; i < m; i++) {
cin >> coins[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m && coins[j] <= i; j++) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
cout << dp[n] << endl;
return 0;
}
```
其中,`n` 表示需找零金额,`m` 表示硬币面值种类数,`coins` 存储硬币面值。
注意,这里使用了 `numeric_limits<int>::max()` 来初始化数组,表示初始状态为无穷大。
阅读全文