A39811. 邮票收集
填空题
较难
知识点
题目描述
邮票收集
题目描述
小A是个邮票收集爱好家，他有n种面值的邮票，每种邮票都有无数张。一天小B想要寄信，需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。
输入
输入是多组数据。(不超过10组) 每组数据的第一行正整数n，k，表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数ai(0 < ai ≤ 1000)。 若n=k=0表示输入结束。
输出
每组数据输出一行一个数，分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案，输出-1。
样例输入
4 10
1 2 3 4
5 16
1 2 3 4 5
2 7
4 5
0 0
样例输出
3
4
-1
提示
第一组数据: 10 = 4+4+2
第二组数据：16 = 5+5+5+1
第三组数据： 不存在。
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1010], f[1010];
int main() {
// 不知道多少组输入，所以死循环
while(1) {
cin >> n >> k;
// 都等于0表示输入结束，退出循环
if(n == 0 and k == 0) {
break;
}
// 初始化 f 数组所有数字为大整数。
memset(f, 127, sizeof(f));
// 预处理 0 元需要 0 张邮票
f[0] = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
// 预处理 a 数组从小到大排序
sort(a + 1, a + n + 1);
// 从 1 元开始递推到 k 元
for(int i = 1; i <= k; i++) {
// 循环查找 a[1], a[2], a[3]... 等金额不大于 i 元的邮票，找最小值
for(int j = 1; j <= n; j++) {
// 因为是从小到大排序的，如果邮票金额大于所需金额，直接退出循环
if(a[j] > i) {
break;
}
// 递推 i 元最少需要多少张邮票
f[i] = min(f[i], f[i - a[j]] + 1);
}
}
// 如果 k 元还是那个最大值，说明已有金额不能组合出 k 元，设为-1
if(f[k] >= (1 << 30)) {
f[k] = -1;
}
cout << f[k] << "\n";
}
return 0;
}
上一题
下一题