如何分割double数组使两部分和差绝对值最小，优化现有C#实现

问题描述 #

给定元素可重复的double类型数组，需拆分为arrA和arrB两个数组，要求两数组和的差值的绝对值最小，返回拆分后的两个数组以及对应的最小绝对差值。原有实现无法覆盖所有场景，存在测试用例不通过的问题。

原有错误实现代码 #

static double Divide_A_B(List<double> args, out List<double> a, out List<double> b)
{
    var array = args;
    int middleIndex = array.Count / 2;
    if (array.Count == 1)
    {
        a = array;
        b = new List<double>();
        return Math.Abs(array[0]);
    }
    else if (array.Count == 2)
    {
        a = new List<double>() { array[0] };
        b = new List<double>() { array[1] };
        return Math.Abs(array[0] - array[1]);
    }
    var (leftArray, rightArray) = (new List<double>(), new List<double>());
    for (int i = 0; i < array.Count; i++)
    {
        if (i <= middleIndex)
        {
            leftArray.Add(array[i]);
        }
        else
        {
            rightArray.Add(array[i]);
        }
    }
    double diff = 0;
    while (true)
    {
        (double leftSum, double rightSum) = (leftArray.Sum(), rightArray.Sum());

        if (leftSum < rightSum)
        {
            var tempArray = leftArray;
            leftArray = rightArray;
            rightArray = tempArray;
            var tempSum = leftSum;
            leftSum = rightSum;
            rightSum = tempSum;
        }
        diff = leftSum - rightSum;
        int flag = 0;
        for (int i = 0; i < leftArray.Count; i++)
        {
            if (leftArray[i] > 0)
            {
                if (leftArray[i] <= diff / 2 || leftArray[i] < diff)
                {
                    rightArray.Add(leftArray[i]);
                    double num = leftArray[i];
                    leftArray.Remove(leftArray[i]);
                    flag++;
                    leftSum -= num;
                    rightSum += num;
                    break;
                }
            }

            for (int j = 0; j < rightArray.Count; j++)
            {
                double diffAfterSwap = Math.Abs((leftSum - leftArray[i] + rightArray[j]) - (rightSum - rightArray[j] + leftArray[i]));
                if (diffAfterSwap < diff)
                {
                    var (targetLeftNum, targetRightNum) = (leftArray[i], rightArray[j]);
                    leftArray.Remove(targetLeftNum);
                    leftArray.Add(targetRightNum);
                    rightArray.Remove(targetRightNum);
                    rightArray.Add(targetLeftNum);
                    flag++;
                    diff = diffAfterSwap;
                    break;
                }
            }

        }

        for (int i = 0; i < rightArray.Count; i++)
        {
            if (rightArray[i] < 0)
            {
                if (Math.Abs(rightArray[i]) <= diff / 2 || Math.Abs(rightArray[i]) < diff)
                {
                    leftArray.Add(rightArray[i]);
                    double num = rightArray[i];
                    rightArray.Remove(rightArray[i]);
                    rightSum -= num;
                    leftSum += num;
                    flag++;
                    break;
                }
            }
            for (int j = 0; j < leftArray.Count; j++)
            {
                double diffAfterSwap = Math.Abs(rightSum - leftSum - 2 * rightArray[i] + 2 * leftArray[j]);
                if (diffAfterSwap < diff)
                {
                    var (targetLeftNum, targetRightNum) = (leftArray[j], rightArray[i]);
                    rightArray.Remove(targetRightNum);
                    rightArray.Add(targetLeftNum);
                    leftArray.Remove(targetLeftNum);
                    leftArray.Add(targetRightNum);
                    flag++;
                    diff = diffAfterSwap;
                    break;
                }
            }
        }
        if (flag == 0)
        {
            break;
        }
    }
    a = leftArray;
    b = rightArray;
    return diff;
}

失败测试用例 #

测试用例数组总和为2892，理想拆分后两数组和均为1446，差值应为0，但原有算法返回差值194。

static void Main(string[] args)
{
    List<double> li = new List<double>() { 310, 226, 231, 218, 291, 267, 321, 332, 352, 344 };
    List<double> a,b = new List<double>();
    double diff = Divide_A_B(li, out a, out b);
    Console.WriteLine("A:");
    foreach (var item in a)
    {
        Console.WriteLine(item);
    }
    Console.WriteLine("B:");
    foreach (var item in b)
    {
        Console.WriteLine(item);
    }
    Console.WriteLine($"diff: { diff}");
    Console.ReadKey();
}

原有代码问题分析 #

• 初始拆分逻辑不合理：直接按索引位置拆分前半段到左数组，完全不考虑元素大小，很容易陷入局部最优，无法得到全局最优解
• 调整逻辑提前跳出：只要找到第一个可移动/交换的元素就直接break，不会选择最优的调整对象，大量能缩小差值的调整被跳过
• 移动判断逻辑冗余有漏洞：leftArray[i] <= diff / 2 || leftArray[i] < diff条件重复，且没有优先选择最接近diff/2的元素移动，调整效率极低
• 缺失排序前置处理：数组排序后可以大幅提升调整效率，也能避免很多无意义的判断

优化后实现方案 #

优化采用「降序排序+贪心初始分配+迭代交换优化」的思路，先排序数组，初始分配时每次把当前元素放到和更小的数组中，之后再遍历所有可能的元素交换进一步缩小差值，直到没有可优化的空间。

static double Divide_A_B(List<double> args, out List<double> a, out List<double> b)
{
    // 前置排序：降序排列
    var sortedArray = args.OrderByDescending(x => x).ToList();
    var leftArray = new List<double>();
    var rightArray = new List<double>();
    double leftSum = 0, rightSum = 0;
    
    // 贪心初始分配
    foreach (var num in sortedArray)
    {
        if (leftSum <= rightSum)
        {
            leftArray.Add(num);
            leftSum += num;
        }
        else
        {
            rightArray.Add(num);
            rightSum += num;
        }
    }

    double diff = Math.Abs(leftSum - rightSum);
    bool hasImprove;
    // 迭代交换优化
    do
    {
        hasImprove = false;
        // 遍历所有可能的交换组合，找最优交换
        for (int i = 0; i < leftArray.Count; i++)
        {
            for (int j = 0; j < rightArray.Count; j++)
            {
                double newDiff = Math.Abs((leftSum - leftArray[i] + rightArray[j]) - (rightSum - rightArray[j] + leftArray[i]));
                if (newDiff < diff)
                {
                    // 执行交换
                    var temp = leftArray[i];
                    leftArray[i] = rightArray[j];
                    rightArray[j] = temp;
                    // 更新和与差值
                    leftSum = leftSum - temp + rightArray[j];
                    rightSum = rightSum - rightArray[j] + temp;
                    diff = newDiff;
                    hasImprove = true;
                    // 找到更优交换后重启遍历，避免遗漏其他优化
                    i = leftArray.Count;
                    j = rightArray.Count;
                }
            }
        }
    } while (hasImprove);

    a = leftArray;
    b = rightArray;
    return diff;
}

优化后代码运行测试用例可得到差值为0的正确结果。

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