请用c++写一题题目描述 小A有n枚硬币,现在要买一样不超过m元的商品,他不想被找零,同时又不想带太多的硬币,且硬币可以重复,现在已知这n枚硬币的价值,请问最少需要多少硬币就能组合成所有可能的价格?输入描述: 第一行两个数:n、m。 下一行,共n个数字,表示硬币的面值。输出描述: 一行一个数,表示最少需要多少硬币。如果无解请输出“No answer!!!”
时间: 2023-03-21 19:00:55 浏览: 78
以下是题目的C语言实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000 // 一个较大的值作为无穷大
int main()
{
int n, m;
int coins[1005]; // 硬币面值数组
int dp[1005]; // 动态规划数组,dp[i]表示组成i元的最少硬币数
int i, j;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", &coins[i]);
}
// 初始化动态规划数组
for (i = 1; i <= m; i++) {
dp[i] = INF;
}
dp[0] = 0;
// 动态规划
for (i = 1; i <= m; i++) {
for (j = 0; j < n; j++) {
if (i >= coins[j] && dp[i-coins[j]] != INF && dp[i-coins[j]] + 1 < dp[i]) {
dp[i] = dp[i-coins[j]] + 1;
}
}
}
// 输出结果
if (dp[m] == INF) {
printf("No answer!!!\n");
} else {
printf("%d\n", dp[m]);
}
return 0;
}
```
其中,用数组 `coins` 存储硬币的面值,用数组 `dp` 存储动态规划的结果,其中 `dp[i]` 表示组成 i 元的最少硬币数。初始化 `dp[0] = 0`,其它的初始化为一个较大的值,这里取 1000000000。然后进行动态规划,对于每一个 i,遍历硬币面值数组 `coins`,如果硬币面值小于等于 i 且 `dp[i-coins[j]]` 不是无穷大且 `dp[i-coins[j]]+1` 小于 `dp[i]`,则更新 `dp[i]` 为 `dp[i-coins[j]]+1`。最后判断 `dp[m]` 是否为无穷大,如果是,则输出 "No answer!!!",否则输出 `dp[m]`。
阅读全文