越越的组队

题意

给出 $n$ 个学生的分数，要从中恰好选出 $n / 2$ 个人。

设全班总分为 sum，要求这 $n / 2$ 个人的总分：

不超过 $sum / 2$
并且尽量大

也就是把一队的人数固定成一半，并让这队总分尽量贴近总分的一半。

思路

先看最直接的暴力：

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;               // 学生人数
int need_cnt;        // 必须选出的人数
int limit_score;     // 选出队伍的总分上限
int a[MAXN];         // 每个学生的分数
int choose_student[MAXN]; // choose_student[i] = 0/1，表示第 i 个学生不选/选
int best_answer;     // 当前找到的最优答案

int calc_count() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_student[i] == 1) cnt++;
    }
    return cnt;
}

int calc_score() {
    int sum_score = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_student[i] == 1) sum_score += a[i];
    }
    return sum_score;
}

bool check() {
    return calc_count() == need_cnt && calc_score() <= limit_score;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_score();
            if (best_answer < value) best_answer = value;
        }
        return;
    }

    // 第 dep 个学生的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_student[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> n;
    need_cnt = n / 2;

    int total_score = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total_score += a[i];
    }

    limit_score = total_score / 2;
    best_answer = 0;
    dfs_choose(1);

    cout << best_answer << '\n';
    return 0;
}

brute.cpp 把每个学生看成一个 01 选择： $choose_student[i] = 0/1$ 表示不选或选。递归先生成完整选择，叶子节点再检查是否恰好选了 $n / 2$ 人，以及总分是否不超过 $floor(sum / 2)$ 。

这个方法很好理解，但复杂度是 $O(2^n)$ ，只能做小数据验证。

这题本质上是 01 背包，只不过除了“总分上限”之外，还多了一个限制：

必须恰好选 $n / 2$ 个人

因此设：

$dp[j][s]$ 表示是否能恰好选 $j$ 个人，使总分恰好为 $s$

加入一个分数 $a[i]$ 时：

不选他：状态不变
选他：如果 $dp[j - 1][s - a[i]]$ 为真，那么 $dp[j][s]$ 也为真

由于每个学生只能选一次，所以 $j$ 和 $s$ 都必须倒序枚举。

状态表

状态	含义
$dp[j][s]$	是否能恰好选 $j$ 人，且总分恰好为 $s$

小例子

如果当前已经处理过分数 2, 3, 4，并且只看“选 2 个人”的可达状态，那么：

选人数	可达总分
`0`	`0`
`1`	`2, 3, 4`
`2`	`5, 6, 7`

这个表说明：DP 其实并不关心具体选了哪几个人，只关心“选了几个人”和“总分是多少”这两个信息。

最后从 $floor(sum / 2)$ 开始倒着找第一个满足 $dp[n / 2][s] = true$ 的 $s$ ，就是答案。

DP 公式

设 $dp_{j,s}$ 表示是否能恰好选 $j$ 个人，使总分恰好为 $s$ 。初始化：

dp_{0,0}=true

处理分数为 $a_i$ 的人时：

dp_{j,s}=dp_{j,s}\lor dp_{j-1,s-a_i}

最终从 $\lfloor sum/2\rfloor$ 开始向下找最大的 $s$ ，满足：

dp_{n/2,s}=true

公式解释： $dp_{j,s}$ 只回答“能不能选出 $j$ 个人总分为 $s$ ”。每加入一个人，就可以把所有少选一个人、少这份分数的可达状态推到新状态；最后找最接近一半总分的可达值。

代码

cpp

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int MAXK = 55;
const int MAXS = 5005;

int n;                  // 学生人数
int need_cnt;           // 必须选出的人数：n / 2
int total_score;        // 全班总分
int limit_score;        // 允许的最大总分：floor(total / 2)
int a[MAXN];            // 每个学生的分数
bool dp[MAXK][MAXS];    // dp[j][s] = 是否能恰好选 j 人，总分恰好为 s

void read_input() {
    cin >> n;
    need_cnt = n / 2;
    total_score = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total_score += a[i];
    }
    limit_score = total_score / 2;
}

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = true;

    for (int i = 1; i <= n; i++) {
        // 人数和分数都要倒序，保证每个学生只被使用一次。
        for (int j = need_cnt; j >= 1; j--) {
            for (int s = limit_score; s >= a[i]; s--) {
                if (dp[j - 1][s - a[i]]) {
                    dp[j][s] = true;
                }
            }
        }
    }

    for (int s = limit_score; s >= 0; s--) {
        if (dp[need_cnt][s]) {
            cout << s << '\n';
            return;
        }
    }

    cout << 0 << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(n * (n / 2) * (sum / 2))$
空间复杂度： $O((n / 2) * (sum / 2))$

总结

看到下面这种条件组合时，要优先想到“附加维度的 01 背包”：

每个元素最多选一次
总和不能超过某个上限
还要额外控制恰好选几个

这题正是把“人数”作为第二维状态，最后在所有合法状态中取最优答案。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

状态表

小例子

DP 公式

代码

复杂度

总结

一图流解析