解题思路

核心问题：将 n 个数分成两组，使得两组和的差值最小（人数可以不同）

这是经典的背包问题/子集和变形。

分析：

• 设总重量为 sum
• 如果能选择一组使得重量尽可能接近 sum/2，那么两组差值最小
• 问题转化为：在 n 个数中选出一部分，使得和尽可能接近 sum/2

动态规划：

• dp[i] 表示是否能凑出重量 i
• 遍历每个体重，更新 dp 数组
• 最后找到最接近 sum/2 的可达到的重量

由于 sum ≤ 100000，可以直接用一维 DP。

时间复杂度：O(n × sum)

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n;
        cin >> n;
        
        vector<int> w(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> w[i];
            sum += w[i];
        }
        
        vector<char> dp(sum + 1, 0);
        dp[0] = 1;
        
        for (int weight : w) {
            for (int j = sum; j >= weight; j--) {
                dp[j] = dp[j] || dp[j - weight];
            }
        }
        
        int target = sum / 2;
        while (target >= 0 && !dp[target]) {
            target--;
        }
        
        cout << sum - 2 * target << endl;
    }
    
    return 0;
}

代码解释

1. 读取测试组数 T
2. 对每组数据：
   • 读取 n 和所有体重
   • 计算总重量 sum
   • 使用 DP 标记可达的重量
   • 找到不超过 sum/2 的最大可达重量
   • 差值 = sum - 2 × target
3. 输出最小差值

复杂度分析

• 时间复杂度：O(T × n × sum)，其中 sum ≤ 100000
• 空间复杂度：O(sum)