不可拆分数值列表的两组最优分组求解

嘿，这个问题其实是经典的均分子集和问题（Partition Problem）的实际应用场景，刚好我之前也处理过类似的需求，给你一步步拆解怎么解决~

问题回顾 #

你给出的待分组数值列表如下：

你的需求是将这些不可拆分的数值分成两组（A和B），使得两组的和尽可能接近（可以相等，也允许存在小差值）。

先修正你给出的示例分组 #

你原来给出的分组（A组30,36和为66，B组23,5,4,1,1和为34）其实不是最接近的组合。先算所有数值的总和：30+36+5+23+1+4+1=100，我们的目标是找到两组和尽可能接近50的组合。

经过计算，最优的分组应该是：

• 分组1：30,23 → 和为53
• 分组2：36,5,4,1,1 → 和为47
  两组差值仅为6，远优于你原来的分组差值32。

通用解决方法 #

这个问题属于NP难问题，但针对小规模数据集（比如你的示例只有7个元素），我们可以用以下简单高效的方法：

1. 核心思路

• 先计算所有数值的总和total_sum，目标是找到一个子集，其和尽可能接近total_sum/2（因为这样两组的差值最小）
• 枚举所有可能的非空真子集（避免重复计算子集和补集），找到和最接近目标值的子集，该子集就是其中一组，剩下的元素为另一组

2. 代码实现（Python）

给你写个简单的可直接运行的脚本，专门处理这种小规模数据集，还能避免重复数值的识别问题：

def find_optimal_partition(numbers):
    total_sum = sum(numbers)
    target = total_sum / 2
    n = len(numbers)
    best_diff = float('inf')
    best_subset_indices = set()

    # 用位掩码枚举所有非空真子集（跳过全集，避免重复计算分组）
    for mask in range(1, 1 << (n - 1)):
        current_indices = set()
        current_sum = 0
        for i in range(n):
            if mask & (1 << i):
                current_indices.add(i)
                current_sum += numbers[i]
        # 计算当前子集和与目标值的差值
        current_diff = abs(current_sum - target)
        # 更新最优解
        if current_diff < best_diff:
            best_diff = current_diff
            best_subset_indices = current_indices

    # 生成最优分组
    group1 = [numbers[i] for i in best_subset_indices]
    group1_sum = sum(group1)
    group2 = [numbers[i] for i in range(n) if i not in best_subset_indices]
    group2_sum = sum(group2)

    return (group1, group1_sum), (group2, group2_sum)

# 代入你的示例数据
quantities = [30, 36, 5, 23, 1, 4, 1]
group_a, group_b = find_optimal_partition(quantities)
print(f"最优分组A: {group_a[0]} → 和为{group_a[1]}")
print(f"最优分组B: {group_b[0]} → 和为{group_b[1]}")

3. 大数据量场景的处理

如果你的数据集很大（比如超过20个元素），暴力枚举就会变得很慢，这时候可以用动态规划的方法：

• 用一个布尔数组dp，其中dp[i]表示是否能凑出和为i的子集
• 从target值往下遍历，找到最大的i使得dp[i]为True，这个i就是最接近目标的子集和
• 回溯推导对应的子集元素即可

补充说明 #

如果你的数据集里存在大量重复数值，或者数值范围很大，也可以考虑用贪心算法快速得到一个近似最优解（但注意贪心不一定能得到绝对最优解，比如当存在一个极大数值时，贪心可能会出错）。

备注：内容来源于stack exchange，提问作者Soundarya Raja