最小邮票数（动态规划）：有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值

邮票数（动态规划）：有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值"/>

最小邮票数（动态规划）：有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值

题目链接：最小邮票数

题目描述：

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。     如，有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>
int main(){int m;int dp[100];while(scanf("%d", &m)!=EOF){int n, lst[20];scanf("%d", &n);  //读取邮票数for(int i=0; i<101; i++) dp[i]=n+1;  //初始化空间数组int x=0;while(1){  //读取邮票面值scanf("%d", &lst[x]);x++;if(getchar()=='\n') break;}dp[0]=0;  //0分需要0张邮票dp[lst[0]]=1;for(int i=1; i<n; i++){for(int j=m; j>=lst[i]; j--){if(dp[j-lst[i]]+1<dp[j])dp[j] = dp[j-lst[i]]+1;}}if(dp[m]<=n)printf("%d\n", dp[m]);elseprintf("%d\n", 0);}return 0;
}