如何将偶数元素集合划分为两个等元素子集且和尽可能接近？求算法

这个问题属于等大小子集和分割问题，是经典NP难问题的变种——如果集合规模n不大（比如n≤40），我们可以用精确算法找到最优解；如果n很大，就用启发式近似算法快速得到接近最优的结果。

一、精确解法：动态规划 #

核心思路是跟踪两个状态维度：已选择的元素数量、已选元素的总和。我们用状态记录「选k个元素能否得到总和s」，最后在所有满足k=n/2的s中，找最接近总总和一半的那个。

伪代码实现 #

输入：集合S（元素为浮点数，长度n为偶数）
输出：两个子集A和B，各含n/2个元素，和尽可能接近

1. 计算集合总总和total_sum = sum(S)
2. 目标参考和target = total_sum / 2
3. 需要选择的元素个数k = n / 2

4. 初始化动态规划状态：用字典dp，key是已选元素个数，value是该个数能达到的所有和的集合
   - 初始时dp[0] = {0}，其他key对应的集合为空

5. 遍历每个元素num in S:
   - 反向遍历i从k-1到0（避免重复选择同一个元素）：
     - 如果i不在dp中，跳过
     - 遍历当前dp[i]中的所有和s:
       - 将s+num加入dp[i+1]（如果dp[i+1]不存在则先创建空集合）

6. 在dp[k]的所有和s中，找到最接近target的那个，记为best_sum
7. 回溯找到对应的k个元素组成子集A，剩下的元素组成子集B
8. 返回A和B

针对示例的说明 #

你的示例集合总和是28.9，target是14.45。通过动态规划，我们会找到k=5时最接近14.45的和（14.5和14.4），然后回溯得到对应的两个子集。

二、近似解法：改进贪心算法（适合大规模n） #

如果n很大，动态规划的时间/空间开销会爆炸，这时候可以用启发式贪心：先排序，再交替把最大元素分配给当前和较小的子集，最后再做局部调整优化。

伪代码实现 #

输入：集合S（元素为浮点数，长度n为偶数）
输出：两个子集A和B，各含n/2个元素，和尽可能接近

1. 将S按降序排序
2. 初始化子集A、B，初始和sumA=0，sumB=0
3. 遍历排序后的每个元素num:
   - 如果sumA <= sumB 且 len(A) < n/2:
       将num加入A，sumA += num
   - else if len(B) < n/2:
       将num加入B，sumB += num
   - else:
       // 如果其中一个子集已满，尝试调整：找A中比num小的元素，替换后让sumA和sumB更接近
       遍历A中的元素a:
           新sumA' = sumA - a + num
           新sumB' = sumB + a
           如果abs(new_sumA' - new_sumB') < abs(sumA - sumB):
               将a移到B，num加入A，更新sumA和sumB，跳出循环
       // 如果A里找不到合适的，尝试调整B
       遍历B中的元素b:
           新sumB' = sumB - b + num
           新sumA' = sumA + b
           如果abs(new_sumA' - new_sumB') < abs(sumA - sumB):
               将b移到A，num加入B，更新sumA和sumB，跳出循环

4. 返回A和B

这个方法在你的示例中，排序后的集合是[5.0,5.0,5.0,4.0,3.1,2.9,1.6,1.0,0.7,0.6]，按照规则分配后会快速得到接近最优的结果，甚至直接命中最优解。

内容的提问来源于stack exchange，提问作者Ramiro