清华大学---最小邮票数（动态规划）

题目描述
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
输入描述:
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
输出描述:
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
示例1
输入
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;  
}