基于递归C++的最小和划分算法问询：物品重量均衡分组问题

Hey，咱们来搞定这个经典的分组问题：现在有N个物品，重量分别是s₁、s₂……sₙ，得把它们分成两组，让两组的总重量尽可能接近。我参考了Abhiraj Smit的递归思路，给你整理出完整的实现代码和逻辑说明：

完整递归实现代码 #

// 用于解决最小和划分问题的递归C++程序
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

// 寻找最小差值的核心递归函数
int findMinRec(int arr[], int i, int sumCalculated, int sumTotal) {
    // 递归终止条件：已经遍历完所有元素
    if (i == 0) {
        // 计算两组重量的差值绝对值：sumTotal - sumCalculated是另一组的重量，两者相减取绝对值
        return abs((sumTotal - sumCalculated) - sumCalculated);
    }

    // 递归两种选择：将当前元素加入已计算总和的组，或者不加入
    return min(
        findMinRec(arr, i - 1, sumCalculated + arr[i - 1], sumTotal),
        findMinRec(arr, i - 1, sumCalculated, sumTotal)
    );
}

// 对外暴露的调用函数，用于计算最小差值
int findMin(int arr[], int n) {
    // 先计算所有物品的总重量
    int sumTotal = 0;
    for (int i = 0; i < n; i++) {
        sumTotal += arr[i];
    }

    // 调用递归函数，从最后一个元素开始，初始已计算总和为0
    return findMinRec(arr, n, 0, sumTotal);
}

// 测试示例
int main() {
    int arr[] = {1, 6, 11, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "两组重量的最小差值为: " << findMin(arr, n) << endl;
    return 0;
}

核心逻辑拆解 #

这个递归方法的思路其实很直白：

• 递归终止条件：当我们遍历完所有物品（i == 0）时，直接计算当前划分方案下两组的重量差，返回其绝对值。
• 递归选择分支：对于每个物品，我们有两种处理方式：把它放到其中一组（更新sumCalculated），或者不放到这组（保持sumCalculated不变）。我们递归这两种情况，取返回的最小差值。
• 总重量前置计算：在调用递归函数前，先算出所有物品的总重量，这样在递归里就能快速得到另一组的重量。

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