没有采用动态规划，而是尝试了深度优先搜索，代码丑陋，贴出来丰富一下大家的思路

#include<iostream>
using namespace std;
// M为邮票总值，n为邮票张数，minNum为用到的最少的张数
// N为邮票面额 
int M, n, minNum;
int N[20];
// index为邮票的编号，Num为当前用到的邮票张数，Sum为用到的邮票总面额 
void DFS(int index, int Num, int Sum){
    if(index == n){
        if(Sum == M && Num < minNum){
            minNum = Num;
        }
        return;
    }
    DFS(index + 1, Num + 1, Sum + N[index + 1]);
    DFS(index + 1, Num, Sum);
}
int main(){
    // 给minNum一个大于等于20的初值 
    minNum = 20;
    while(cin >> M){
        cin >> n;
        for(int i = 0; i < n; i++){
            cin >> N[i];
        }
        // 初始index为-1 
        DFS(-1, 0, 0);
        if(minNum == 20){
            minNum = 0;
        }
        cout << minNum << endl;
    }
    return 0;
}

#include<stdio.h>
int dp[20][105],Max=99999999;
int main(){
	int v[50],N,i,j,M;
	while(scanf("%d",&M)!=EOF){
		for(scanf("%d",&N),i=0;i<N;i++) scanf("%d",&v[i]);
		for(i=0;i<N;i++) dp[i][0]=0;
		for(j=0;j<=M;j++)
			if(j==v[0]) dp[0][j]=1;
			else dp[0][j]=Max;
		for(i=1;i<N;i++)
			for(j=1;j<=M;j++){
				dp[i][j]=dp[i-1][j];
				if(j>=v[i]&&dp[i][j]>dp[i-1][j-v[i]]+1)
					dp[i][j]=dp[i-1][j-v[i]]+1;
			}
		printf("%d\n",dp[N-1][M]<Max?dp[N-1][M]:0);
	}
}

#include <iostream>
#include <math.h>
using namespace std;
int main(){
    int m, n, v[50], dp[20][100], Max = 99999999;
    while(scanf("%d",&m)!=EOF&&m>0){
        scanf("%d", &n);
        if(n==0){
            printf("0\n");
            break;
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i]);
        for(int i=0;i<=m;i++)
            dp[0][i] = Max;
        for(int i=0;i<=n;i++)
            dp[i][0] = 0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                if(v[i]>j) dp[i][j] = dp[i-1][j];
                else
                    dp[i][j] = min(1+dp[i-1][j-v[i]], dp[i-1][j]);
            }
        if(dp[n][m]==Max) printf("0\n");
        else printf("%d\n",dp[n][m]);
    }
}

dfs,bfs都可以，速度都差不多

package com.speical.first;

import java.util.Scanner;

/** 
* 邮票问题
* 
* dfs
* 因为一张有票可以使用一次，所以dfs其实也挺快的
* 不用变量来维持就小
* 根据dfs特性，最后一个成功的，必然是数量最小的那个路径
* @author special
* @date 2017年12月21日 下午3:54:17
*/
public class Pro13 {
    private static int sum;
    private static int[] nums;
    private static int minCount;

    public static void dfs(int index, int add, int count){
        if(add == sum) {
            minCount = count;
            return;
        }
        for(int i = index + 1; i < nums.length; i++)
            dfs(i, add + nums[i], count + 1);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            sum = input.nextInt();
            int n = input.nextInt();
            nums = new int[n];
            for(int i = 0; i < n; i++)
                nums[i] = input.nextInt();
            minCount = 0;
            dfs(-1,0,0);
            System.out.println(minCount);
        }
    }

}

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int M, N;
	while (cin>>M>>N)
	{
		int* P = new int[N];//面值
		for (int i = 0; i < N; i++)
			cin >> P[i];

		//dp数组表示将第i个邮票加入集合后 凑总量为j的面额 所需要的最少邮票数量
		int* dp = new int[M + 1];
		//base case
		for (int j = 0; j <= M; j++)
			dp[j] = M;
		dp[0] = 0;
		//状态转移
		for (int i = 0; i < N; i++)
			for (int j = M; j >= P[i]; j--)
				dp[j] = min(dp[j], dp[j - P[i]] + 1);
		if (dp[M] == M)//说明所有邮票加起来也凑不出来
			dp[M] = 0;
		cout << dp[M] << endl;
		delete[] P, dp;
	}
	return 0;
}

// 由于样本数据集较小，采用dsp的方法写的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 20;

int value[maxn] = {0};          // 存储邮票的面值

int main()
{
    
    int m;
    int n;
    while(cin >> m)
    {

        cin >> n;
        for(int i = 0; i < n; ++i)
        {
            cin >> value[i];
        }

        // 0-2^n-1
        int end = (1<<n) - 1;
        int count = -1;
        int sum = 0;
        int tmp = 0;
        for(int i = 0; i <= end; ++i)
        {
            sum = 0;
            tmp = 0;
            // cout << i << ":";
            for(int j = 0; j < n; ++j)
            {
                // cout << (i & (1 << j)) << " ";
                if(i & (1 << j))
                {
                    sum += value[j];
                    tmp ++;
                }
            }
            // cout << endl;
            if(sum == m)
            {
                if(count == -1)
                {
                    count = tmp;
                }
                else
                {
                    count = count < tmp ? count : tmp;
                }
            }
        }
        if(count == -1)
        {
            cout << 0 << endl;
        }
        else
        {
            cout << count << endl;
        }
    }


    return 0;
}

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。

我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：

1. 当j-v[i-1] >= 0且dp[i-1][j-v[i-1]]!=INT32_MAX时，dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + 1)
2. 当j-v[i-1] < 0或dp[i-1][j-v[i-1]]==INT32_MAX时，dp[i][j] = dp[i-1][j]
3. 基准1: dp[..][0] = 0
4. 基准2: dp[0][1..] = INT32_MAX(用INT32_MAX表示不能凑齐)

状态公式的解释如下：

1. 当前邮票面值小于等于所需总面值时，最小邮票张数为选择当前邮票和不选择当前邮票两种情况中的较小者
2. 当前邮票面值大于所需面值时，无法将当前邮票加入
3. 当所需总面值为0时，所需最小邮票张数为0
4. 当邮票张数为0，所需总面值不为0时，无法凑齐

//
// Created by jt on 2020/8/26.
//
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int M, N;
    cin >> M >> N;
    vector<int> v;
    for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back(a); }
    vector<vector<int> > dp(N + 1, vector<int>(M + 1, INT32_MAX));
    for (int i = 0; i <= N; ++i) { dp[i][0] = 0; }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            // 如果可以选择当前邮票
            if (j >= v[i-1] && dp[i-1][j-v[i-1]] != INT32_MAX) {
                dp[i][j] = min(dp[i-1][j-v[i-1]] + 1, dp[i-1][j]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    if(dp[N][M] == INT32_MAX) cout << 0 << endl;
    else cout << dp[N][M] << endl;
}

#include<vector>
(721)#include<iostream>
using namespace std;


int main() {
    int m, n;
    while(cin>>m>>n) {
        vector<int> stamps(n, 0);
        for(int i=0; i<n; ++i) cin>>stamps[i];
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i=0; i<=m; ++i) dp[0][i]=10000;
        for(int i=0; i<=n; ++i) dp[i][0]=0;
        
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=m; ++j) {
                if(stamps[i-1] <= j)
                    dp[i][j]=min(dp[i-1][j], dp[i-1][j-stamps[i-1]]+1);
                else
                    dp[i][j]=dp[i-1][j];
            }
        }
        if(dp[n][m]==10000) cout<<0<<endl;
        else cout<<dp[n][m]<<endl;
    }
}

#include <stdio.h>
int a[20];
int count(int m,int top)
{
    int min=20;
    for(int i=top; i>=0; i--)
    {
        if(a[i]==m)
        {
            return 1;
        }
        if(a[i]<m)
        {
            int temp=count(m-a[i],i-1);
            if(temp && temp<min)
            {
                min=temp;
            }
        }
    }
    if(min-20)
    {
        return min+1;
    }
    return 0;
}
int main()
{
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        printf("%d\n",count(m,n-1));
    }
    return 0;
}

0-1背包问题变种（求最小邮票数）可以视value值均为1，以下是空间优化后的代码，dp从二维降到一维，具体原理可参考csdn blog，很多有写到空间优化的思路。

总结：最小邮票数问题为0-1背包问题变种（即不可重复选多张邮票，只能选或不选）

            找零钱问题为完全背包问题变种（即可重复选多张钞票）

 

//从后往前遍历，因为不可以有重复的。 
#include <bits/stdc++.h>
using namespace std;
int main(){
	int m,n,w[110],dp[1010]={0};
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
		for(int i=1;i<=m;i++){
			dp[i]=1<<30;
		} 
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			dp[j]=min(dp[j],dp[j-w[i]]+1);
			
		}
	}

	if(dp[m]<(1<<30))cout<<dp[m];
	else cout<<0;
	return 0;
}

/*
    动态规划，01背包问题，这次求的是最小值
    
    状态表示 f[i][j] 只从前i张邮票里面选，总价值>=j,花的最小邮票的数量
      
    状态计算         1.如果j=0，那么无解，如果i=0，那么也无解,结果为0         2.将集合分为包含第i张的和不包含第i张的
            如果不包含第i张，那么f[i][j]=f[i-1][j]
            如果包含第i张，那么f[i][j] = min(f[i][j],f[i-1][j-v[i]]+w[i]);             所以状态计算就是f[i][j] = min(f[i-1][j],f[i-1][j-v[i]]+1)
    然后再用滚动数组将其优化一下变成一维的就好
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
const int inf = 1<<30; // 非法状态
int v[maxn];
int f[maxn];
int m,n;
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>v[i]; // input
	for(int i=1;i<=m;i++) f[i] = inf; // 因为要求的是恰好凑到，那么一开始除了0之外其他都没有合法的解
	for(int i=1;i<=n;i++)
		for(int j=m;j>=v[i];j--)
			f[j] = min(f[j],f[j-v[i]]+1);
	if(f[m]<inf)
		cout<<f[m]<<endl;
	else
		cout<<0<<endl;
}

//回溯法（dfs） 注意剪枝
#include <iostream>
(720)#include <algorithm>
#include <vector>

using namespace std;

(3420)#define INF 0x7F7F7F

int m;		//邮票面值
int n;		//张数
vector <int> v;

vector <int> x;
int min_n = INF;

int select_cnt()
{
	int cnt = 0;
	for (auto i : x)
		if (i == 1)
			cnt++;
	return cnt;
}

void dfs(int i, int total, int remain)
{
	if (i == n)
	{
		if (total == m && select_cnt() < min_n)
			min_n = select_cnt();
	}
	else
	{
		if (total + remain - v[i] >= m)				//不选择
		{
			x[i] = 0;
			dfs(i + 1, total, remain - v[i]);
		}
		if (total + v[i] <= m)					//选择
		{
			x[i] = 1;
			dfs(i + 1, total + v[i], remain - v[i]);
		}
	}	
}

int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		int num; cin >> num;
		v.push_back(num);
		x.push_back(0);
	}

	int remain = 0;
	for (auto i : v)
		remain += i;

	dfs(0, 0, remain);
	min_n = min_n == INF ? 0 : min_n;
	cout << min_n;
}

//动态规划，注意从后往前遍历
#include <iostream>
(720)#include <algorithm>
#include <vector>

using namespace std;

(3420)#define INF 0x7F7F7F

int m;		//邮票面值
int n;		//张数
vector <int> v;

int func()
{
	vector<int>dp(m + 1);
	for (int i = 0; i <= m; i++)
		dp[i] = i == 0 ? 0 : INF;
	for (int i = 0; i < n; i++)
	{
		for (int j = m; j >= 0; j--)
		{
			if (j >= v[i])
				dp[j] = min(dp[j], dp[j - v[i]] + 1);
		}
	}
	return dp[m];
}

int main()
{
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		int num; cin >> num;
		v.push_back(num);
	}

	int res = func();
	res = res == INF ? 0 : res;
	cout << res << endl;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int m, n;  // 集齐m，  n张邮票
    const int INF = 1000;
    while (cin >> m >> n) {
        int stamp[n + 1];
        int dp[n + 1][m + 1]; // 前n个邮票，集齐m， 所需要的邮票数
        /*
         dp[i][j] 前i个邮票，集齐j， 所需要的邮票数
         -若第i个邮票不放入，则相当于前i-1张邮票要集齐j， dp[i][j] = dp[i - 1][j]
         -若第j个邮票放入，则相当于前i-1张邮票，集齐j-stamp[i],然后票数加一， dp[i][j] = dp[i - 1][j - stamp[i]] + 1;
         两者取最小值， dp[i][j] = min{dp[i - 1][j], dp[i - 1][j - stamp[i]] + 1 | j > stamp[i]}
         dp[n][m]即为所求。
         那么dp数组如何初始化？边界值设置为几？
         根据定义 -当dp[0...n][0]时，不管有多少张邮票，都要凑成0，则显而易见，一张邮票都不用就行，所以dp[0...n][0] = 0
                 - 当dp[0][1...m]时，没有一张邮票给你，但是要凑 大于0的数，则不可能，所以dp[0][1...m] = INF  (一个很大的数，别是INT_MAX，会爆int)

         做完以上工作，下来就是套01背包的板子
         */
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j == 0) dp[i][j] = 0;
                else dp[i][j] = INF;
            }
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &stamp[i]);
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = m; j >= stamp[i]; --j) {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - stamp[i]] + 1);
            }
        }
        int res = (dp[n][m] == INF) ? 0 : dp[n][m];
        cout << res << endl;
    }
    return 0;
}

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cmath>
#include <limits>

using namespace std;

const int INT_INF = numeric_limits<int>::max();
int m;
int ans = INT_INF;
int post[20];
int n;
void func(int sum,int num,int i){
	if(sum==m){  //凑成功，不断取最小值
		ans = min(ans,num);
		return ;
	}
	if(sum <m && i<n && num<ans){  //不满足时可减去枝丫
		func(sum+post[i],num+1,i+1);
		func(sum,num,i+1);
	}
}

int main(){
	while(cin>>m && m!=0){
		cin>>n;
		for(int i=0;i<n;i++)
			cin>>post[i];
		//输入完毕

		sort(post,post+n,greater<int>());  //排序，大的在前，方便减枝
		func(0,0,0);
		if(ans==INT_INF) cout<<0<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}