最少邮票个数

首先，这是一个背包问题。描述转化为“背包”，有N个物品，每个物品的质量为Vi，背包重量为M，求最少取多少个物品才能刚好装满背包，如果无法满足条件，返回0。

我们用INT32_MAX表示无法凑齐，设dp[i][j]为邮票为前i张时，刚好凑成j所需要的最小邮票张数，有以下状态公式：

1. 当j-v[i-1] >= 0且dp[i-1][j-v[i-1]]!=INT32_MAX时，dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i-1]] + 1)
2. 当j-v[i-1] < 0或dp[i-1][j-v[i-1]]==INT32_MAX时，dp[i][j] = dp[i-1][j]
3. 基准1: dp[..][0] = 0
4. 基准2: dp[0][1..] = INT32_MAX(用INT32_MAX表示不能凑齐)

状态公式的解释如下：

1. 当前邮票面值小于等于所需总面值时，最小邮票张数为选择当前邮票和不选择当前邮票两种情况中的较小者
2. 当前邮票面值大于所需面值时，无法将当前邮票加入
3. 当所需总面值为0时，所需最小邮票张数为0
4. 当邮票张数为0，所需总面值不为0时，无法凑齐

代码如下：

//
// Created by jt on 2020/8/26.
//
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int M, N;
    cin >> M >> N;
    vector<int> v;
    for (int i = 0; i < N; ++i) { int a; cin >> a; v.push_back(a); }
    vector<vector<int> > dp(N + 1, vector<int>(M + 1, INT32_MAX));
    for (int i = 0; i <= N; ++i) { dp[i][0] = 0; }
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            // 如果可以选择当前邮票
            if (j >= v[i-1] && dp[i-1][j-v[i-1]] != INT32_MAX) {
                dp[i][j] = min(dp[i-1][j-v[i-1]] + 1, dp[i-1][j]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    if(dp[N][M] == INT32_MAX) cout << 0 << endl;
    else cout << dp[N][M] << endl;
}