将n个砝码分配到双手使两手重量差最小的问题求解

这个问题本质是经典的0-1背包变种，核心目标是从所有砝码中选出一个子集放在其中一只手，让子集的总重量尽可能接近所有砝码总重量的一半，这样两只手的重量差值自然最小。

方案1：回溯法（适用于砝码数量n<20的小数据场景） #

穷举所有可能的砝码子集，计算每个子集的总重量和总重量一半的差值，记录最优的子集即可，逻辑简单直接。

def min_weight_diff(weights):
    total = sum(weights)
    half = total / 2
    best_sum = 0
    best_subset = []
    
    def backtrack(index, current_sum, current_subset):
        nonlocal best_sum, best_subset
        # 剪枝：当前和已经超过一半，继续加砝码只会离最优解更远
        if current_sum > half:
            return
        # 更新最优解
        if current_sum > best_sum:
            best_sum = current_sum
            best_subset = current_subset.copy()
        # 遍历剩下的砝码选择是否放入当前子集
        for i in range(index, len(weights)):
            current_subset.append(weights[i])
            backtrack(i+1, current_sum + weights[i], current_subset)
            current_subset.pop()
    
    backtrack(0, 0, [])
    other_subset = [w for w in weights if w not in best_subset]
    return best_subset, sum(best_subset), other_subset, sum(other_subset), abs(sum(best_subset)*2 - total)

# 测试示例
weights = [5,8,4]
subset1, sum1, subset2, sum2, diff = min_weight_diff(weights)
print(f"左手砝码：{subset1}，总重{sum1}")
print(f"右手砝码：{subset2}，总重{sum2}")
print(f"最小差值：{diff}")

• 优点：无额外空间开销，实现简单，能100%得到最优解
• 缺点：时间复杂度为O(2^n)，n超过20之后运行速度会急剧下降

方案2：动态规划法（适用于n较大、总重量不超过1e5的场景） #

用dp数组记录是否能凑出重量为j的子集，最终找到不超过总重量一半的最大可凑出重量即可，效率远高于回溯法。

def min_weight_diff_dp(weights):
    total = sum(weights)
    half = total // 2
    # dp[j]表示是否能凑出重量为j的子集
    dp = [False] * (half + 1)
    dp[0] = True
    # 记录路径，方便输出具体分配方案
    prev = [[] for _ in range(half + 1)]
    
    for w in weights:
        # 倒序遍历避免重复选择同一个砝码
        for j in range(half, w-1, -1):
            if dp[j - w] and not dp[j]:
                dp[j] = True
                prev[j] = prev[j - w] + [w]
    # 找到不超过half的最大可凑出重量
    max_j = max([j for j in range(half+1) if dp[j]])
    subset1 = prev[max_j]
    sum1 = max_j
    subset2 = [w for w in weights if w not in subset1]
    sum2 = total - sum1
    return subset1, sum1, subset2, sum2, abs(sum1 - sum2)

# 测试示例
weights = [5,8,4]
subset1, sum1, subset2, sum2, diff = min_weight_diff_dp(weights)
print(f"左手砝码：{subset1}，总重{sum1}")
print(f"右手砝码：{subset2}，总重{sum2}")
print(f"最小差值：{diff}")

• 优点：时间复杂度为O(n*总重量)，在总重量不大的情况下运行速度极快
• 缺点：如果砝码总重量超过1e6，会占用过多内存，可改用滚动数组优化空间占用，或者用位运算进一步优化执行效率

方案选择建议 #

• 砝码数量少于20个：直接使用回溯法
• 砝码数量多但总重量不超过1e5：优先使用动态规划法
• 砝码总重量极大且对精度要求不是100%的场景：可以使用模拟退火、遗传算法等启发式算法求近似最优解

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