设有 n 种不同面值的硬币,各硬币的面值存于数组 T[1:n]中。现要用这些 面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组 Coins[1:n]中。 对任意钱数 0≤m≤20001,设计一个用最少硬币找钱 m 的方法。 输入: 输入的第一行中只有 1 个整数给出 n 的值,第 2 行起每行 2 个数,分别 是 T[j]和 Coins[j]。最后 1 行是要找的钱数 m。 输出: 程序运行结束时,将计算出的最少硬币数输出。问题无解时输出-1。使用c++来实现代码并列出
时间: 2024-02-18 09:04:56 浏览: 20
好的,请看以下代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 20010;
const int INF = 1e9;
int n, m;
int T[MAXN], Coins[MAXN];
int dp[MAXN];
int main() {
// 输入数据
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> T[i] >> Coins[i];
}
cin >> m;
// 初始化 dp 数组
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
// 动态规划
for (int i = 1; i <= n; i++) {
for (int j = T[i]; j <= m; j++) {
if (dp[j - T[i]] != INF && Coins[i] > 0) {
dp[j] = min(dp[j], dp[j - T[i]] + 1);
Coins[i]--;
}
}
}
// 输出结果
if (dp[m] == INF) {
cout << -1 << endl;
} else {
cout << dp[m] << endl;
}
return 0;
}
```
这份代码首先通过输入读入 n、T 数组、Coins 数组和 m。然后,初始化 dp 数组为一个很大的数,dp[0] = 0。接下来,使用两层循环,遍历每个硬币面值 T[i],从 T[i] 逐个递增到 m,依次更新 dp 数组。对于每个钱数 j,如果 dp[j-T[i]] 不等于很大的数,说明可以使用一个面值为 T[i] 的硬币,将钱数从 j-T[i] 转移过来,dp[j-T[i]] 表示找钱数为 j-T[i] 时所需的最少硬币数,加 1 表示使用了一个面值为 T[i] 的硬币。然后,Coins[i] 减 1,表示使用了一个 T[i] 的硬币。最后,如果 dp[m] 的值为一个很大的数,说明无法找零,输出-1,否则输出 dp[m]。
希望我的解答能够帮助到你!