红军物资均衡分配 题解

题目分析

我们有 $n$ 件物资，每件物资 $i$ 有一个重量 $w_i$。需要对每件物资做出决策：

1. 分配给第一纵队，使第一纵队的累计重量增加 $w_i$；
2. 分配给第二纵队，使第二纵队的累计重量增加 $w_i$；
3. 作为战略预备，不计入任何一队的重量，但会消耗预备名额。

全局有两个限制：

• 两支纵队最终获得的总重量必须相等，即重量差为 $0$；
• 留作预备的物资总数不能超过 $m$。

求所有满足条件的分配方案数。注意，如果 $n \le m$，允许所有物资都留作预备（两队重量均为 $0$，差为 $0$）。

解题思路

本题并没有给出 $n$ 的具体范围，但从参考代码的实现方式（直接回溯）可以看出，$n$ 不会太大，否则单纯的指数级搜索会超时。通常这种题目的 $n$ 在 $20$ 左右，是一个典型的**深度优先搜索（DFS）**问题。

核心思想是：枚举每件物资的三种去向，并在过程中维护当前的两队重量差与预备数量，到达末尾时检查是否满足条件。

我们需要维护的状态有三个：

• 当前处理到第几件物资（从 $0$ 到 $n$）；
• 当前第一纵队总重量减去第二纵队总重量的差值 diff；
• 当前已经留作预备的物资件数 reserve_cnt。

搜索树的每一个分支对应一种选择，当所有物资处理完毕时，若 diff == 0 且 reserve_cnt <= m，则计数器加一。

算法说明

DFS 回溯

定义递归函数：

cpp
复制
1void dfs(int idx, int diff, int reserve_cnt)

• idx：当前考虑的物品下标（0-based）。
• diff：第一纵队重量 - 第二纵队重量。
• reserve_cnt：已经选择作为预备的物资数量。

递归过程：

1. 剪枝：如果 reserve_cnt > m，已经超过预备上限，不可能再合法，直接返回。
2. 递归出口：当 idx == n 时，所有物品处理完毕。此时若 diff == 0，说明两队重量相等，记录一种方案（ans++），然后返回。
3. 递归扩展：对于当前物品 w[idx]，有三种选择：
   • 分给第一纵队：diff 增加 w[idx]，预备数不变，处理下一件。
     dfs(idx + 1, diff + w[idx], reserve_cnt)
   • 分给第二纵队：diff 减小 w[idx]，预备数不变。
     dfs(idx + 1, diff - w[idx], reserve_cnt)
   • 留作预备：diff 不变，预备数加一。
     dfs(idx + 1, diff, reserve_cnt + 1)

最终答案累加在全局变量 ans 中。

为什么这样搜索是正确的？

我们并不关心两队的绝对重量，只关心它们的差值。初始时两队的重量都是 $0$，差值为 $0$。每分给一队一件物资，差值就向对应方向偏移该物资的重量。最终若差值回到 $0$，则两队重量必然相等。这种方式避免了同时记录两个队伍的重量，大大简化了状态表示。

至于预备物资，只需计数即可，因为它们的重量不影响差值。

对参考代码的补充解释

参考代码中的 DFS 没有任何记忆化或复杂的剪枝，只是单纯的暴力搜索。它能够正确计算出所有方案，但时间复杂度较高。

时间复杂度分析

每件物资有 $3$ 种选择，递归树是一棵 $3$ 叉树，深度为 $n$。
最坏情况下需要遍历所有 $3^n$ 种分配方案。
因此时间复杂度为 $O(3^n)$。

当 $n$ 较小时（例如 $n \le 20$，$3^{20} \approx 3.5 \times 10^9$，在 C++ 中会超时），实际运行会非常慢。本题判定为“困难”，可能 $n$ 非常小，或者允许用更高级的优化（如 折半搜索 meet-in-the-middle）才能通过更大的数据。参考代码给出的是一种最朴素的解法，易于理解，但在 $n$ 较大时不可行。

空间复杂度为 $O(n)$，来自递归调用栈。

参考代码

cpp
复制
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int n, m;
7vector<int> w;
8long long ans = 0; // 方案数可能很大，使用 long long
9
10/**
11 * @param idx: 当前处理到的物资下标 (0 到 n)
12 * @param diff: 纵队1总重 - 纵队2总重
13 * @param reserve_cnt: 当前已选为预备的物资数量
14 */
15void dfs(int idx, int diff, int reserve_cnt) {
16    // 剪枝：如果预备物资数量超过限制，直接返回
17    if (reserve_cnt > m) return;
18
19    // 基准情况：所有物资都处理完了
20    if (idx == n) {
21        // 如果两队重量差为0，说明分配公平，找到一种合法方案
22        if (diff == 0) {
23            ans++;
24        }
25        return;
26    }
27
28    // 策略 1: 分给第一纵队
29    dfs(idx + 1, diff + w[idx], reserve_cnt);
30
31    // 策略 2: 分给第二纵队
32    dfs(idx + 1, diff - w[idx], reserve_cnt);
33
34    // 策略 3: 留作预备
35    dfs(idx + 1, diff, reserve_cnt + 1);
36}
37
38int main() {
39    // 优化输入输出效率
40    ios_base::sync_with_stdio(false);
41    cin.tie(NULL);
42
43    if (cin >> n >> m) {
44        w.resize(n);
45        for (int i = 0; i < n; ++i) {
46            cin >> w[i];
47        }
48
49        dfs(0, 0, 0);
50
51        cout << ans << endl;
52    }
53
54    return 0;
55}

代码说明：

1. 使用 vector<int> w 存储所有物品重量。
2. ans 定义为 long long，防止方案数超出 int 范围。
3. dfs 函数按照上面的算法描述实现，逻辑清晰。
4. 主函数中读取 $n, m$ 和重量数组后，调用 dfs(0,0,0) 从第 $0$ 件物品、差值为 $0$、预备数 $0$ 开始搜索。
5. 最后输出累计的方案数 ans。

可能的优化方向

如果题目数据规模较大，可以考虑以下优化：

• 记忆化搜索：将状态 (idx, diff, reserve_cnt) 存储下来，但由于 diff 可能非常大（所有重量之和），直接使用数组或 map 存储状态会造成较大开销。如果重量范围不大，可以用偏移数组做 DP。
• 折半搜索 (Meet-in-the-Middle)：将物品分成两半，分别枚举所有可能的 (diff, reserve_cnt) 组合，然后在两边合并统计，将复杂度降为 $O(3^{n/2})$。这是解决指数级搜索的常用手段。
• 动态规划：可将问题转化为子集和计数问题，但需要考虑预备数量限制，设计三维 DP，复杂度约为 $O(n \cdot m \cdot \sum w_i)$，在重量总和不大时可行。

本题参考代码给出的是最直接的搜索方案，便于理解问题的本质，同时也是实现后续优化的基础。