题解 | #最小邮票数#

#include<iostream>
#include<algorithm>
using namespace std;


int main(){
    const int MAXN = 1000000000;
    //前多少张邮票，能凑到多少钱
    int M,N;
    while(cin>>M>>N){
        int a[105] = {0},W[25][105] = {0};
        for(int i = N; i >= 1; i--) cin>>a[i];//变成降序排列
        for(int i = 1; i <= M; i++) W[0][i] = MAXN;
        for(int i = 1; i <= N; i++) W[i][0] = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= M; j++){
                if(j>=a[i]) W[i][j] = min(W[i-1][j],W[i-1][j-a[i]]+1);
                else W[i][j] = W[i-1][j];
            }
        }
        if(W[N][M]==MAXN) cout<<0<<endl;
        else cout<<W[N][M]<<endl;
    }
    return 0;
}

使用动态规划。
1.动态规划的矩阵，行表示前i件元素，列表示总价值为j，元素值表示选取的最小个数。
2.动态规划从1开始进行，对应的a[i]从1开始，表示第i件物品的价值。
3.对于每个元素，当前的钱为a[i]，可以有两种选择：
（1）如果选第i件物品，则W[i][j] = W[i-1][j-a[i]]+1，表示当前的最小数量等于前i-1物品的最小数量+1，但是前提是第i件物品的价值不会超过总价值。
（2）如果不选第i件物品，则W[i][j] = W[i-1][j]。表示当前的最小数量等于前i-1件物品的最小数量。
两者之中取最小值
4.边界条件：
如果i=0，j!=0，表示前i件物品中选择价值为j的数量，这是不可能实现的，为了不选，设置为一个极大值。
如果j=0，说明前i件物品中选择价值为i的数量，这时候选择0件即可实现，设置为0。
5.结果的处理：
如果结果时极大值，说明选不到，输出为0；否则矩阵最后一个元素就是最小的元素数量。打印输出即可。