题解 | #最小邮票数#

#include <climits>
#include <iostream>
#include <cstring>
#include <iterator>


using namespace std;

const int N = 30;
const int M = 110;

int a[N];
int dp[N][M];


int main(){

    /*
    dp[i][j]表示前i张邮票构成的邮票总值为j的所需要的最少邮票数
    每张邮票选or不选：
        不选：dp[i][j]=dp[i-1][j]
        选：dp[i][j]=dp[i-1][j-a[i]]+1
    dp[n][m]为构成m总值的邮票最少数
    dp[n][m]=INT_MAX 表示无解
    */
    int n,m;
    while(cin>>m>>n){
        for(int i=1;i<=n;i++)cin>>a[i];
        memset(dp,0x3f,sizeof(dp));
        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++){
                dp[i][j]=dp[i-1][j];
                if(j>=a[i])dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]+1);//因为dp[i][0]=0,故更新后dp[i][j]刚好为1，且j等于a[i];
            }
        }
        if(dp[n][m]==0x3f3f3f3f)cout<<0<<endl;
        else cout<<dp[n][m]<<endl;
    }

    return 0;
}