每日算法 — 使用java实现拔河：子集划分与回溯算法

游戏背景与问题建模

拔河是一项考验团队配合的经典竞技游戏。在正式比赛前，教练需要将若干名选手分成两队，使两队总体实力尽可能接近。本文将这一实际问题抽象为子集划分问题（Subset Partition Problem）：给定一个整数数组表示每位选手的实力值，将其划分为两个子集，使得两个子集的元素和之差最小。

该问题是经典的 NP-完全问题，对于小规模数据可通过回溯搜索精确求解，对于大规模数据可采用动态规划或近似算法。

算法思路

回溯搜索 + 剪枝

核心思路是枚举每个选手归属 A 队或 B 队，递归搜索所有可能的分配方案，记录最优解。为提高效率，引入以下剪枝策略：

• 平衡剪枝：若当前两队实力差已超过已知最优解，直接返回。
• 排序预处理：将选手按实力降序排列，优先分配实力强的选手，更快逼近最优解。

算法步骤

1. 对所有选手实力值按降序排序。
2. 从第 0 位选手开始，尝试将其分配到 A 队或 B 队。
3. 递归处理下一位选手，同时维护当前两队的累计实力。
4. 当所有选手分配完毕，更新全局最小实力差。
5. 回溯撤销当前分配，尝试另一分支。

Java 完整实现

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

/**
 * 拔河队伍分配：子集划分与回溯算法
 * 目标：将选手划分为两队，使两队实力和最接近
 */
public class TugOfWar {

    private int minDiff;           // 全局最小实力差
    private boolean[] bestAssignment; // 最优分配方案
    private int totalSum;          // 所有选手实力总和

    /**
     * 求解拔河最优分队
     * @param strengths 每位选手的实力值数组
     * @return 两队分配结果
     */
    public TeamAllocation solve(int[] strengths) {
        int n = strengths.length;
        if (n == 0) return new TeamAllocation(new ArrayList<>(), new ArrayList<>(), 0);

        // 降序排序：优先分配实力强的选手，增强剪枝效果
        int[] sorted = strengths.clone();
        Arrays.sort(sorted);
        // 转为降序
        for (int i = 0; i < n / 2; i++) {
            int tmp = sorted[i];
            sorted[i] = sorted[n - 1 - i];
            sorted[n - 1 - i] = tmp;
        }

        totalSum = Arrays.stream(sorted).sum();
        minDiff = Integer.MAX_VALUE;
        bestAssignment = new boolean[n];
        boolean[] current = new boolean[n];

        // 从第0位选手开始回溯
        backtrack(sorted, 0, 0, 0, current);

        // 构建结果
        List<Integer> teamA = new ArrayList<>();
        List<Integer> teamB = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (bestAssignment[i]) {
                teamA.add(sorted[i]);
            } else {
                teamB.add(sorted[i]);
            }
        }
        return new TeamAllocation(teamA, teamB, minDiff);
    }

    /**
     * 回溯搜索核心方法
     * @param sorted    降序排列的实力数组
     * @param index     当前处理的选手下标
     * @param sumA      A队当前累计实力
     * @param sumB      B队当前累计实力
     * @param current   当前分配状态
     */
    private void backtrack(int[] sorted, int index, int sumA, int sumB, boolean[] current) {
        int n = sorted.length;

        // 边界：所有选手已分配
        if (index == n) {
            int diff = Math.abs(sumA - sumB);
            if (diff < minDiff) {
                minDiff = diff;
                System.arraycopy(current, 0, bestAssignment, 0, n);
            }
            return;
        }

        // 剪枝1：若当前差值已不小于最优解，直接返回
        int currentDiff = Math.abs(sumA - sumB);
        if (currentDiff >= minDiff) {
            return;
        }

        // 剪枝2：乐观估计——即使剩余全部分给较弱队，也无法超越当前最优
        int remaining = 0;
        for (int i = index; i < n; i++) {
            remaining += sorted[i];
        }
        int optimisticDiff = Math.abs(sumA - sumB) - remaining;
        if (optimisticDiff < 0) optimisticDiff = 0;
        if (optimisticDiff >= minDiff) {
            return;
        }

        // 尝试将当前选手分配给 A 队
        current[index] = true;
        backtrack(sorted, index + 1, sumA + sorted[index], sumB, current);

        // 尝试将当前选手分配给 B 队
        current[index] = false;
        backtrack(sorted, index + 1, sumA, sumB + sorted[index], current);
    }

    /**
     * 动态规划解法（适用于规模较大的情况）
     * 将问题转化为：在数组中选取若干元素，使其和最接近 totalSum/2
     */
    public TeamAllocation solveDP(int[] strengths) {
        int n = strengths.length;
        int sum = Arrays.stream(strengths).sum();
        int target = sum / 2;

        // dp[i][j] 表示前 i 个元素能否组成和为 j
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= strengths[i - 1] && dp[i - 1][j - strengths[i - 1]]) {
                    dp[i][j] = true;
                }
            }
        }

        // 找到最接近 target 的可行和
        int bestSum = 0;
        for (int j = target; j >= 0; j--) {
            if (dp[n][j]) {
                bestSum = j;
                break;
            }
        }

        // 回溯还原选取的元素
        List<Integer> teamA = new ArrayList<>();
        List<Integer> teamB = new ArrayList<>();
        int i = n, j = bestSum;
        while (i > 0) {
            if (j >= strengths[i - 1] && dp[i - 1][j - strengths[i - 1]]) {
                teamA.add(strengths[i - 1]);
                j -= strengths[i - 1];
            } else {
                teamB.add(strengths[i - 1]);
            }
            i--;
        }

        return new TeamAllocation(teamA, teamB, sum - 2 * bestSum);
    }

    // 结果封装类
    public static class TeamAllocation {
        public final List<Integer> teamA;
        public final List<Integer> teamB;
        public final int diff;

        public TeamAllocation(List<Integer> teamA, List<Integer> teamB, int diff) {
            this.teamA = teamA;
            this.teamB = teamB;
            this.diff = diff;
        }

        @Override
        public String toString() {
            return String.format("A队: %s (总和=%d)%nB队: %s (总和=%d)%n实力差: %d",
                    teamA, teamA.stream().mapToInt(Integer::intValue).sum(),
                    teamB, teamB.stream().mapToInt(Integer::intValue).sum(), diff);
        }
    }

    public static void main(String[] args) {
        TugOfWar solver = new TugOfWar();

        int[] strengths = {85, 90, 78, 92, 88, 76, 95, 82};
        System.out.println("=== 回溯算法 ===");
        TeamAllocation result = solver.solve(strengths);
        System.out.println(result);

        System.out.println("\n=== 动态规划算法 ===");
        TeamAllocation resultDP = solver.solveDP(strengths);
        System.out.println(resultDP);
    }
}

复杂度分析

回溯算法在最坏情况下需要遍历所有 2^n 种分配方案，但通过排序和双重剪枝，实际运行效率远高于理论上限。动态规划解法将问题转化为 0-1 背包的变种，适用于选手实力值总和不太大的场景。

扩展思考

• 人数不等的情况：若要求两队人数差不超过 1，可在回溯时增加人数约束。
• 多目标优化：除了实力均衡，还可考虑位置搭配、经验互补等因素，引入加权评分函数。
• 遗传算法近似：对于大规模选手（如 50 人以上），可采用遗传算法在多项式时间内获得近似最优解。