C++背包DP 邮票问题怎么写

邮票问题是一个经典的背包问题。假设有n种不同面值的邮票，每种邮票的面值分别为a1, a2, ..., an。现在要用这些邮票凑出一个给定的邮资m，问最少需要几张邮票。

这个问题可以使用动态规划来解决。定义一个一维数组dp，其中dp[i]表示凑出邮资i所需要的最少邮票数。初始时，将dp数组的所有元素初始化为无穷大。

然后，遍历dp数组的每个元素，对于每个元素dp[i]，遍历所有的邮票面值，假设当前邮票面值为ai，那么需要判断是否可以使用这张邮票来凑出邮资i。如果可以，那么更新dp[i]的值，将其更新为dp[i-ai]+1。这里要注意，如果dp[i-ai]的值为无穷大，表示无法使用ai邮票来凑出邮资i，所以需要跳过这种情况。

最后，dp[m]的值就是凑出邮资m所需要的最少邮票数。

下面是用C++代码实现邮票问题的动态规划解法：

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int main() {
    int n; // 邮票的种类数
    cin >> n;

    vector<int> stamps(n); // 邮票面值数组
    for (int i = 0; i < n; i++) {
        cin >> stamps[i];
    }

    int m; // 邮资
    cin >> m;

    vector<int> dp(m + 1, INT_MAX); // dp数组，初始值为无穷大
    dp[0] = 0; // 邮资为0时，需要0张邮票

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

    if (dp[m] == INT_MAX) {
        cout << "Impossible" << endl; // 无法凑出邮资m
    } else {
        cout << dp[m] << endl; // 最少需要dp[m]张邮票
    }

    return 0;
}

以上代码根据输入的邮票种类数、面值数组和邮资，输出最少需要的邮票数。如果无法凑出邮资m，则输出"Impossible"