题目链接：http://pipioj.online/problem.php?id=1599

题意重述

给定 n 个数字，每个数字可以被重复使用。
目标是凑出和为 m，问最少要用多少个数字；如果凑不出，输出 -1。

数据范围（单组）：

  • 1 <= n <= 500
  • 1 <= m <= 1000
  • 数字 x 满足 0 <= x <= 1000
  • 多组测试 T <= 100

思路

这是标准的「完全背包求最少件数」。

定义 dp[s]：凑出和 s 所需的最少数字个数。
初始化：

  • dp[0] = 0
  • 其余 dp[s] = INF

转移（每个数字可重复使用）：

dp[s] = min(dp[s], dp[s - x] + 1)，其中 s >= x。

因为是“可重复使用”，所以同一个数字 x 时，s 要从小到大遍历。

最后：

  • dp[m] 仍是 INF，输出 -1
  • 否则输出 dp[m]

时间复杂度 O(n * m)，空间复杂度 O(m)。

C++17 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;

        vector<int> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];

        const int INF = 1e9;
        vector<int> dp(m + 1, INF);
        dp[0] = 0;

        for (int x : a) {
            if (x <= 0 || x > m) continue;
            for (int s = x; s <= m; ++s) {
                if (dp[s - x] != INF) {
                    dp[s] = min(dp[s], dp[s - x] + 1);
                }
            }
        }

        cout << (dp[m] == INF ? -1 : dp[m]) << '\n';
    }

    return 0;
}

样例解释

输入：

1
2
3
4
5
2
3 6
1 2 3
2 3
2 4
  • 第 1 组：6 = 3 + 3，最少用 2 个
  • 第 2 组：用 2 和 4 不可能凑出 3，所以是 -1

易错点

  1. 这是“每个数字可重复选取”，不是 01 背包。
  2. 数字里可能有 0，对凑正数没有帮助，转移时可直接跳过。
  3. 多组数据下，每组都要重新初始化 dp。