时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：2252
解决：741
- 题目描述：
-
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。
如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
- 输入：
-
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
- 输出：
-
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
- 样例输入：
-
10
5
1 3 3 3 4
- 样例输出：
-
3
思路：
由于已经排好序了，就不用再排。优先选大额邮票尝试，因为这样张数少。
代码：
#include <stdio.h> #define N 100
#define M 100 int minStep;
int m;
int a[N]; void pick(int sum, int n, int step)
{
if (sum == m)
{
if (step < minStep)
minStep = step;
return;
}
if (sum > m || n == 0)
return;
pick(sum+a[n-1], n-1, step+1);
pick(sum, n-1, step);
} int main()
{
int i, n; while(scanf("%d%d", &m, &n) != EOF)
{
for (i=0; i<n; i++)
scanf("%d", &a[i]);
minStep = M;
pick(0, n, 0); if (minStep == M)
printf("0\n");
else
printf("%d\n", minStep);
}
return 0;
}
/**************************************************************
Problem: 1209
User: liangrx06
Language: C
Result: Accepted
Time:40 ms
Memory:912 kb
****************************************************************/