写一个用C++背包问题做的邮票问题

#include #include #include using namespace std;

int main() { int n; // 邮票种类数量 int m; // 邮资 cout << "请输入邮票种类数量："; cin >> n; cout << "请输入需要凑齐的邮资："; cin >> m;

vector<int> stamps(n); // 邮票面值
cout << "请输入每种邮票的面值：" << endl;
for (int i = 0; i < n; i++) {
    cin >> stamps[i];
}

sort(stamps.begin(), stamps.end(), greater<int>()); // 面值从大到小排序

vector<int> dp(m + 1, m + 1); // 动态规划数组，初始化为m+1
dp[0] = 0; // 邮资为0时需要的邮票数量为0

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

if (dp[m] == m + 1) {
    cout << "无法凑齐邮资" << endl;
} else {
    cout << "需要的最少邮票数量为：" << dp[m] << endl;
}

return 0;