如何将整数集合分组为等和Bin？寻求高效系统解决方案

问题概述 #

给定已减去平均值的整数数组，目标是将其划分为指定数量的组，每组元素数量固定且和为0。针对小规模和大规模数据，分别提供可行的解决思路：

小规模数据（如示例45元素分3组） #

对于小规模数据，可采用回溯+剪枝的精确搜索方法，通过优先处理绝对值大的元素减少搜索空间，快速找到可行解。

实现代码 #

import numpy as np

X = np.array([-2368, -2143, -1903, -1903, -1888, -1648, -1528, -1318, -1213,
              -1153, -1033,  -928,  -793,  -703,  -508,  -493,  -463,  -448,
               -418,  -358,  -223,  -118,   -88,   137,   227,   257,   347,
                347,   377,   557,   632,   632,   692,   812,   827,  1007,
               1022,  1262,  1352,  1727,  1892,  2267,  2297,  2327,  2642])

# 按绝对值从大到小排序，优先处理难匹配的大元素
sorted_X = sorted(X, key=lambda x: -abs(x))
group_size = 15
num_groups = 3
target_sum = 0

# 记录每组当前和与元素列表
groups = [{"sum": 0, "elements": []} for _ in range(num_groups)]

def backtrack(index):
    if index == len(sorted_X):
        # 验证所有组是否符合要求
        for g in groups:
            if len(g["elements"]) != group_size or g["sum"] != target_sum:
                return False
        return True
    
    current_num = sorted_X[index]
    for i in range(num_groups):
        g = groups[i]
        # 剪枝1：组内元素已达上限，跳过
        if len(g["elements"]) >= group_size:
            continue
        # 剪枝2：放入当前元素后，剩余元素无法凑到目标和，跳过
        remaining_slots = group_size - len(g["elements"]) - 1
        max_possible_adjust = sum(abs(x) for x in sorted_X[index+1:index+1+remaining_slots])
        if abs(g["sum"] + current_num) > max_possible_adjust:
            continue
        # 剪枝3：跳过重复状态（同和同元素数的组，放入当前元素效果一致）
        skip = False
        for j in range(i):
            if groups[j]["sum"] == g["sum"] and len(groups[j]["elements"]) == len(g["elements"]):
                skip = True
                break
        if skip:
            continue
        
        # 尝试放入当前元素
        g["sum"] += current_num
        g["elements"].append(current_num)
        
        if backtrack(index + 1):
            return True
        
        # 回溯
        g["sum"] -= current_num
        g["elements"].pop()
    
    return False

if backtrack(0):
    print("找到可行分组：")
    for idx, g in enumerate(groups):
        print(f"组{idx+1}（和：{g['sum']}，元素数：{len(g['elements'])}）：")
        print(g["elements"])
else:
    print("未找到可行分组")

大规模数据（百万级元素分1000组） #

大规模数据下，精确搜索完全不可行，需采用启发式算法在可接受时间内找到近似解，并通过局部调整优化至可行解。

1. 贪心算法（高效易实现） #

核心思路：优先处理大元素，每次将元素放入当前最接近目标和的组，用堆优化查找效率。

实现代码

import heapq
import numpy as np

def greedy_grouping(arr, num_groups, group_size):
    # 按绝对值从大到小排序
    sorted_arr = sorted(arr, key=lambda x: -abs(x))
    # 小顶堆存储（当前和绝对值，当前和，元素数量，元素列表），快速找到最接近目标的组
    heap = []
    for _ in range(num_groups):
        heapq.heappush(heap, (0, 0, 0, []))
    
    for num in sorted_arr:
        abs_sum, current_sum, count, elements = heapq.heappop(heap)
        # 放入元素并更新组状态
        new_sum = current_sum + num
        new_count = count + 1
        new_elements = elements.copy()
        new_elements.append(num)
        heapq.heappush(heap, (abs(new_sum), new_sum, new_count, new_elements))
    
    # 提取所有组
    return [heapq.heappop(heap) for _ in range(num_groups)]

# 示例测试
X = np.array([-2368, -2143, -1903, -1903, -1888, -1648, -1528, -1318, -1213,
              -1153, -1033,  -928,  -793,  -703,  -508,  -493,  -463,  -448,
               -418,  -358,  -223,  -118,   -88,   137,   227,   257,   347,
                347,   377,   557,   632,   632,   692,   812,   827,  1007,
               1022,  1262,  1352,  1727,  1892,  2267,  2297,  2327,  2642])

groups = greedy_grouping(X, 3, 15)
for idx, (abs_s, s, c, els) in enumerate(groups):
    print(f"组{idx+1}：和={s}，元素数={c}")

局部调整优化

若贪心结果存在组和不为0的情况，可执行以下调整：

• 遍历所有组，找到和为正的组A与和为负的组B。
• 在A中找一个元素a，在B中找一个元素b，使得交换后A的和(sum_A -a +b)与B的和(sum_B -b +a)更接近0。
• 重复上述操作，直到所有组和为0。

2. 模拟退火算法（高质量近似解） #

适合对解质量要求较高的场景，通过随机交换元素并按概率接受较差解，避免陷入局部最优：

1. 随机生成初始分组（保证每组元素数量正确）。
2. 计算当前解的代价（所有组和的绝对值之和）。
3. 随机交换两个不同组的元素，计算新解代价。
4. 根据退火温度决定是否接受新解：代价更低则直接接受；代价更高时，按exp(-Δ代价/温度)的概率接受。
5. 逐步降低温度，重复步骤3-4，直到找到可行解或温度降至阈值。

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