题解 | #最小邮票数#

0-1背包问题，选取邮票，满足总额的条件下求最小的邮票数

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int main(){
    int M,N;
    while(cin>>M>>N){
        int v[N];
        for(int i=0;i<N;i++){
            cin>>v[i];
        }
        int dp[M+1] ;
        for (int i = 0; i < M+1; i++) {dp[i] = 0x7fff0000;}
//         memset(&dp,0,M+1);
        dp[0] = 0;
        for(int i=0;i<N;i++){
            for(int j=M;j>=v[i];j--){
                dp[j] = min(dp[j],dp[j-v[i]]+1);
            }
        }
        if(dp[M] == 0x7fff0000)cout<<0<<"\n";
        else {cout<<dp[M]<<"\n";}
    }
}