题目描述 小A有n枚硬币,现在要买一样不超过m元的商品,他不想被找零,同时又不想带太多的硬币,且硬币可以重复,现在已知这n枚硬币的价值,请问最少需要多少硬币就能组合成所有可能的价格?输入描述: 第一行两个数:n、m。 下一行,共n个数字,表示硬币的面值。输出描述: 一行一个数,表示最少需要多少硬币。如果无解请输出“No answer!!!”
时间: 2023-03-21 19:00:55 浏览: 377
算法思路:
本题可以使用动态规划的思想进行解答,定义dp[i]为组合出面值为i所需的最少硬币数目,则有转移方程:
dp[i] = min(dp[i], dp[i - coins[j]] + 1) (其中coins[j]表示第j个硬币的面值,i - coins[j] 表示使用第j个硬币后剩余的面值)
其中,初始化 dp[0] = 0,表示组合出面值为0所需的硬币数目为0。同时,为避免无解情况的发生,可以将dp数组初始化为正无穷,若最终dp[m]仍然为正无穷,则输出“No answer!!!”
最终的答案为dp[m],即组合出面值为m所需的最少硬币数目。
Python 代码实现:
相关问题
请用c++写一题题目描述 小A有n枚硬币,现在要买一样不超过m元的商品,他不想被找零,同时又不想带太多的硬币,且硬币可以重复,现在已知这n枚硬币的价值,请问最少需要多少硬币就能组合成所有可能的价格?输入描述: 第一行两个数:n、m。 下一行,共n个数字,表示硬币的面值。输出描述: 一行一个数,表示最少需要多少硬币。如果无解请输出“No answer!!!”
以下是题目的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]`。
题目描述 Sousi所在世界的货币有各种不同的面值。今天,会魔法的Sousi在她的储物袋里放了两种面值不同的硬币,每种硬币都有 n枚,准备到集市上购买炼制魔法药水的材料。经过仔细的挑选后,Sousi总共购买了价值为m的材料。现在她想知道能否恰好用这两种硬币付款,而没有任何找零。 输入格式 一行,包含四个整数a,b,n,m,分别表示两种硬币的面值,每种硬币的数量,以及购买的材料的价值。 输出格式 若可以恰好表示,则输出“YES”,否则输出“NO”(不包含引号)。c++代码
好的,下面是这道题的 C++ 代码实现:
```c++
#include <iostream>
using namespace std;
int main()
{
int a, b, n, m;
cin >> a >> b >> n >> m;
for (int i = 0; i <= n; i++) {
int j = (m - i * a) / b;
if (j >= 0 && j <= n && i * a + j * b == m) {
cout << "YES" << endl;
return 0;
}
}
cout << "NO" << endl;
return 0;
}
```
我们通过循环枚举第一种硬币使用的个数 i,然后计算使用第二种硬币的个数 j = (m - i * a) / b,若 j 是一个整数且 j 不超过 n,则说明可以恰好用这两种硬币付款,输出 "YES",否则输出 "NO"。
阅读全文