//第二次做这个题目了，比第一次更难受
//这次用的是动态规划
#include<iostream>
#include<vector>
#define mmax 0x7fffffff
using namespace std;
int min(int a,int b){return a<b?a:b;}
int main()
{
    int m,n;
    while(cin>>m)
    {
/*****************读取数据区域****************************/
        cin>>n;
        vector<int> c(n);
        for(int i=0;i<n;i++)
            cin>>c[i]; 
/*****************读取数据区域****************************/
        
/*****************初始化区域****************************/
        vector<int> dp(m+1);
        for(int i=0;i<=m;i++)
            dp[i]=mmax;
        dp[0]=0;
/*****************初始化区域****************************/
        
/*****************循环体区域****************************/
/*方法大概类似于筛选法，
  题目中已经给出有序，不需要再次排序，
  对于每一个邮票来说，有且仅有一次使用机会
  所以遍历所有邮票，获取邮票的面值，
  对于每一个dp数组来说，dp[i]中的i代表总值，dp[i]中保存的数据为个数，
  遍历所有小于等于m的i，如果总值减去当前所选的邮票的面值，即i-c[i]合法并且可达
   那么i一定可达，
  并且dp[i]中的值应该是dp[i-c[i]]的值+1和原来的值中较小的一个。
  想想第二层循环，循环所有小于等于m的i时，为什么要倒序？*/
        for(int i=0;i<n;i++)  
        {                     
            for(int j=m;j>=0;j--)  
            {
                if(j-c[i]>=0&&dp[j-c[i]]!=mmax)
                {
                    dp[j]=min(dp[j],dp[j-c[i]]+1);
                }
            }
        }
/*****************循环体区域****************************/
        
/*****************输出数据区域****************************/
        if(dp[m]==mmax) cout<<0<<endl;
        else cout<<dp[m]<<endl;
/*****************输出数据区域****************************/
    }
}

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

#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>

using namespace std ;

#define maxn 110

#define maxm 999999

int a[ maxn ], dp[ maxn ];

void init(){

    for ( int i= 0 ;i< maxn ;i++) dp [i]= maxm ;

}

int main(){

    int n,m;

    while ( cin >>m>>n){

        init ();

        for ( int i= 0 ;i<n;i++) cin >> a [i];

       dp [ 0 ]= 0 ;

        for ( int i= 0 ;i<n;i++){

            for ( int j=m;j>= a [i];j--){

                dp [j]= min ( dp [j], dp [j- a [i]]+ 1 );

            }

        }

        cout <<( dp [m]== maxm ? 0 : dp [m])<< endl ;

    }

    return 0 ;

}

#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;
}