递归如何遍历所有组合？苹果分组最小重量差递归方案答疑

问题描述 #

现有n个重量已知的苹果，需分成两组使重量差最小：

• 输入：整数n（苹果数量），随后一行是n个整数p₁,p₂,…,pₙ（苹果重量）
• 示例输入：

5
3 2 7 4 1

• 示例输出：1
• 解释：组1重量为2、3、4（总重9），组2重量为1、7（总重8）
• 约束条件：1 ≤ n ≤ 20，1 ≤ pᵢ ≤ 10⁹

递归解决方案代码 #

def divide_apples(index, group1_weight, group2_weight, apple_weights):
    # Base case: If all apples have been considered, return the difference in weights
    if index == len(apple_weights):
        return abs(group1_weight - group2_weight)
    
    # Recursive calls:
    # Include current apple weight in group 1
    diff1 = divide_apples(index + 1, group1_weight + apple_weights[index], group2_weight, apple_weights)
    # Include current apple weight in group 2
    diff2 = divide_apples(index + 1, group1_weight, group2_weight + apple_weights[index], apple_weights)
    
    # Return the minimum difference obtained
    return min(diff1, diff2)

# Main code
n = int(input())  # Read the number of apples
apple_weights = list(map(int, input().split()))  # Read the apple weights

# Call the divide_apples function with initial values
minimum_difference = divide_apples(0, 0, 0, apple_weights)
print(minimum_difference)

疑问解答 #

1. 递归是如何遍历所有组合的？ #

这个递归函数的核心逻辑其实就是逐个处理每个苹果，对每个苹果做两种选择：

• 把当前苹果放到组1
• 把当前苹果放到组2

从index=0（第一个苹果）开始，每一层递归都会分叉出两个子调用，分别对应上述两种选择。直到index等于苹果总数（所有苹果都处理完）时，计算当前两组的重量差并返回。

比如拿2个苹果举例：

• 第一层递归（index=0）：分叉出“苹果1进组1”和“苹果1进组2”两个分支
  • 分支1（苹果1进组1）：进入index=1，再分叉出“苹果2进组1”和“苹果2进组2”
    • 苹果2进组1：index=2，返回|(p1+p2)-0|
    • 苹果2进组2：index=2，返回|p1-p2|
  • 分支2（苹果1进组2）：进入index=1，再分叉出“苹果2进组1”和“苹果2进组2”
    • 苹果2进组1：index=2，返回|p2-p1|
    • 苹果2进组2：index=2，返回|0-(p1+p2)|

每一条从根到叶子的路径，都对应一种苹果分组的组合。递归通过这种分叉遍历了所有可能的分组方式，最后在每一步取两个分支中的最小差值向上传递，最终得到所有组合里的最小重量差。

2. 难道最终两组重量差必为0？ #

当然不是。只有当苹果总重量是偶数，且存在子集重量等于总重量的一半时，差才会是0。如果总重量是奇数，或者总重量是偶数但没有子集能达到总重的一半，那最小差就不可能是0。

比如示例输入的总重量是3+2+7+4+1=17（奇数），所以两组重量差最小只能是1（17=9+8，9-8=1），不可能达到0。递归函数会遍历所有组合，找到那个最接近总重一半的分组，返回对应的最小差值。

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