写一个用C++背包问题做的邮票问题给定一个信封最多只允许粘贴n�n≤100�≤100张邮票我们现在有m�m≤100�≤100种邮票面值分别为：x1x2……xm�1�2……��分xi≤255��≤255为正整数并假设各种邮票都有足够多张。要求计算所能获得的邮资最大范围。即求最大值MAX���使在1⋯MAX1⋯���之间的每一个邮资值都能得到。输入格式第一行为一个整数n�含义如题所述第二行为一个整数m

#include #include #include using namespace std;

int main() { int n, m; cin >> n >> m;

vector<int> stamps(m);
for (int i = 0; i < m; i++) {
    cin >> stamps[i];
}

// dp[i]表示邮资为i时最少需要的邮票数
vector<int> dp(n + 1, 10001);
dp[0] = 0;

for (int i = 0; i < m; i++) {
    for (int j = stamps[i]; j <= n; j++) {
        dp[j] = min(dp[j], dp[j - stamps[i]] + 1);
    }
}

// 查找最大范围
int max_range = 0;
for (int i = 1; i <= n; i++) {
    if (dp[i] == 10001) {
        max_range = i - 1;
        break;
    }
}

cout << max_range << endl;

return 0;