题目翻译#

有 $n$ 队人，每个队人数不同，把他们分成 2 组（同一队的不能拆开），使两组人数差距尽量小。

形式化题意：有 $n$ 个数，把它们分成两组，使两组和的差尽量小。

说句闲话：感觉这题目很经典，但我没有原题作为证据（大雾

解法#

本来觉得我这菜鸡实力是不可能做出来的，~~已经准备摆烂了~~，此时我突然发现 $n \le 20$ 。

这是啥概念？

看图， $n \le 25$ 都是可以用 $O(2 ^ n)$ 做法解决的，这不结束了？直接枚举每一组，分类讨论是 A 组还是 B 组，就可以了。

给个小建议：可以记录总人数，这样子只需要记录 A 组人数，B 组人数可以直接 $O(1)$ 计算，这样就变成选与不选的 dfs 模板题目了……更关键的是这样子不需要记录为每一队对应哪一组了。

代码#

ACCode with 注释：

1
/*Code by Block_Fish*/
2
#include <bits/stdc++.h>
3

4
#define INF 0x3f3f3f3f
5
#define EPS 1e-8
6
#define FOR(i, l, r) for (int(i) = (l); (i) <= (r); ++(i))
7
#define log printf
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<int, int> PII;
18

19
const int N = 30;
20
int n, a[N], ans = INF, sum;
21

22
template <typename T>
23

24
inline T read() {
25
  T sum = 0, fl = 1;
26
  char ch = getchar();
27
  for (; !isdigit(ch); ch = getchar())
28
    if (ch == '-') fl = -1;
29
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
30
  return sum * fl;
31
}
32

33
template <typename T>
34

35
inline void write(T x) {
36
  if (x < 0) {
37
    putchar('-'), write<T>(-x);
38
    return;
39
  }
40
  static T sta[35];
41
  int top = 0;
42
  do { sta[top++] = x % 10, x /= 10; } while (x);
43
  while (top) putchar(sta[--top] + 48);
44
}
45

46
void dfs(int group, int cnt) {
47
  if (group == n) {
48
    ans = min(ans, max(cnt, sum - cnt));
49
    return;
50
  }
51
  // 组 A
52
  dfs(group + 1, cnt + a[group]);
53
  // 组 B
54
  dfs(group + 1, cnt);
55
}
56

57
int main() {
58
  n = read<int>();
59
  FOR(i, 1, n) a[i] = read<int>(), sum += a[i];
60
  dfs(1, 0);
61
  write<int>(ans);
62
  return 0;
63
}
64
// 20组---》爆搜挂着机，打表出 AC