题解 | 常规背包解法，但是设置pair作为容器元素存储邮票数目

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
int main() {
	// M代表邮票总值，N代表邮票数目 
	int M = 0, N = 0;
	while (cin >> M >> N) {
		int num = 0;
		// weight存储每张邮票的面值 
		vector<int> weight(N);
		for (int i = 0; i < N; i++) {
			cin >> weight[i];
		}
		// 设置为pair型为了能够存储邮票数目 
		vector<pair<int, int>> dp(M + 1, {0, 0});
		// 遍历所有邮票 
		for (int i = 0; i < N; i++) {
			// 从背包容量最大为M开始选取 
			for (int j = M; j >= weight[i]; j--) {
				// 一旦数值更大则更新 
				if (dp[j].second < dp[j - weight[i]].second + weight[i]) {
					dp[j].second = dp[j - weight[i]].second + weight[i];
					dp[j].first = dp[j - weight[i]].first + 1;
				}
				// 如果数值相同但所用邮票数目更少则也进行更新 
				else if (dp[j].second == dp[j - weight[i]].second + weight[i] && dp[j].first > dp[j - weight[i]].first + 1) {
					dp[j].first = dp[j - weight[i]].first + 1;
				}
			}
		}
		if (dp[M].second != M) cout << 0 << endl;
		else cout << dp[M].first << endl;
	}
	return 0;
}