题解 | #最小邮票数#

#include<iostream>
#include<limits>
using namespace std;
#define INT_MAX 99999


int main() {
	int weight;
	while (cin>>weight) {
		int w[102],v[102];
		int N; cin >>N;
		for (int i = 0; i < N; i++) {
			cin >> w[i];
			v[i] =1;
		}
		int dp[102];
		dp[0] = 0;
		for (int i = 1; i <= weight; i++) {
			dp[i] = INT_MAX/10 ;
		}
		for (int i = 0; i < N; i++) {
			for (int j = weight; j >=w[i]; j--) {
				dp[j] = min(dp[j], dp[j - w[i]] + v[i]);
			}
		}
		if (dp[weight] == INT_MAX/10) 
		{
			cout << '0' << endl;
		}
		else {
			cout << dp[weight]<<endl;
		}
	}
}