在不重新排列的情况下将数组拆分为大约相等的总和

Question

所以我的这个作业让我很困惑，例如我给出了一个整数数组 210,50,200,100（可以是任何数量或任何数字），我需要将它分成 N 个部分，因此总和基本上相等，差异最小，无需对数字进行排序或重新排列，

例如，210,50,200,300 N = 3；它应该分成 210 250 300（最小和最大之间的差异是 90）

我尝试了一个平均需要 760/3 ~= 253 的程序，并尝试将数字相加，因此它需要 210，看起来添加 50 会使它更接近或远离平均值，所以它添加了 50 冲洗并重复如此它得到 260 200 300 它几乎很好但是 200 和 300 之间的差异是 = 100 所以它不是最佳的因为在没有程序的情况下计算你可以获得更好的结果 210 和 300 只有 90 的差异。

TL:DR 需要一种将 int 数组拆分成大致相等的部分的方法不必相同，只要在不更改位置或数组的情况下尽可能彼此靠近即可。

如果你不想给我方法，请给我伪代码或基本思想，因为我已经坐了几个小时了。

        static int[] Skaiciuoti(int[] knygos, int d)
{
    int[] skyriai = new int[d];
    int n = knygos.Length;
    double sum = knygos.Sum() / d;
    Console.WriteLine(sum);
    int kp = 0;
    for (int i = 0; i < d; i++)
    {

        for (int j = kp; j < n; j++)
        {
            if (i == skyriai.Length - 1)
            {
                skyriai[i] = skyriai[i] + knygos[j];
                kp++;
            }
            else if ((skyriai[i] + knygos[j]) < sum || skyriai[i] == 0)
            {
                skyriai[i] = skyriai[i] + knygos[j];
                kp++;
            }
            else
            {
                break;
            }
        }
    }


    return skyriai;

}

这是我之前尝试过的。

Answer 1

这是一种方法，它类似于您已经尝试过的代码。思路是：

确定 "ideal value" 通过将项目的总和除以部分数 (resultCount) 我们希望将它们拆分为
使用 resultCount 个索引创建一个 result 数组
创建一个 resultIndex 计数器来跟踪我们 result 数组中的哪个索引，我们将把当前 item 添加到
在 foreach 循环中，遍历数组，将每个项目添加到 result 数组中的当前索引，或者，如果这会使我们超过 idealValue ，先增加我们的索引。

例如：

public static int[] Split(int[] input, int resultCount)
{
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (resultCount > input.Length || resultCount < 1)
        throw new ArgumentOutOfRangeException(nameof(resultCount));

    var idealValue = input.Sum() / resultCount;
    var result = new int[resultCount];
    var resultIndex = 0;

    foreach (var item in input)
    {
        // Move to the next index in our result array if the
        // next sum puts us over our expected average amount
        if (result[resultIndex] > 0 &&
            result[resultIndex] + item > idealValue &&
            resultIndex < result.Length - 1)
            resultIndex++;

        result[resultIndex] += item;
    }

    return result;
}

问题在于，如果所有项目都大于我们的 "ideal value"，那么我们 result 数组中的最后一个索引将太大，因为所有内容都被推到那里。要解决这个问题，我们可能需要遍历数组两次，第一次找出每一项的值，第二次用理想的总和填充结果。

考虑输入：

new [] { 1, 1, 1, 1, 1, 1, 1, 1, 10 }, 3  // Split the array into 3 parts

在上面的示例中，sum / parts = 18，所以 idealValue = 6，但实际上我们最终得到的结果看起来像：{ 6, 2, 10 } 而不是 { 4, 4, 10 } ，分布更均匀。

帮助解决此问题的一种方法是删除 "outliers"（那些值大于理想值的项目），然后重新计算一个新的 "ideal" 值。这让我们更接近完美：

public static int[] Split(int[] input, int resultCount)
{
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (resultCount > input.Length || resultCount < 1)
        throw new ArgumentOutOfRangeException(nameof(resultCount));

    var idealValue = input.Sum() / resultCount;
    var result = new int[resultCount];
    var resultIndex = 0;

    // Recalculate idealValue by removing items over the ideal
    var itemsUnder = input.Where(item => item <= idealValue).ToList();
    idealValue = itemsUnder.Sum() / (resultCount - (input.Length - itemsUnder.Count));

    foreach (var item in input)
    {
        // Move to the next index in our result array if the
        // next sum puts us over our expected average amount
        if (result[resultIndex] > 0 &&
            result[resultIndex] + item > idealValue &&
            resultIndex < result.Length - 1)
            resultIndex++;

        result[resultIndex] += item;
    }

    return result;
}

现在输入：

new [] { 1, 1, 1, 1, 1, 1, 1, 1, 10 }, 3  // Split the array into 3 parts

我们先计算idealValue = 6，然后我们忽略10，把剩下的除以(3 - 1)，得到一个new idealValue = 4，我们最终得到的结果看起来像 { 4, 4, 10 }，分布更均匀。

这仍然无助于我们最终将许多较小的数字汇总到最后一个索引中的情况（因为没有其他地方可以放置它们）。

例如，如果我们有一个像 {80, 99, 60, 200, 50, 70, 90} 这样的输入，我们将首先计算一个 idealValue = 216（因为 none 的项目超过那个数额，第二次重新计算时不会改变）。但是当我们运行它通过我们的第一次迭代时，我们最终得到结果集：{179, 60, 410}。请注意，所有靠近末尾的较小值都被转储到最后一个位置。

处理那个问题的一种方法是在生成第一个结果集后重新计算idealValue。如果需要通过检查小于 idealValue 的项目之间是否有足够大的差异我们可以修复来重新计算结果，我们只想这样做：

public static int[] Split(int[] input, int resultCount)
{
    if (input == null) throw new ArgumentNullException(nameof(input));
    if (resultCount > input.Length || resultCount < 1)
        throw new ArgumentOutOfRangeException(nameof(resultCount));

    var idealValue = input.Sum() / resultCount;
    var result = new int[resultCount];
    var resultIndex = 0;

    // Recalculate idealValue by removing items over the ideal
    var itemsUnder = input.Where(item => item <= idealValue).ToList();
    idealValue = itemsUnder.Sum() / (resultCount - (input.Length - itemsUnder.Count));

    foreach (var item in input)
    {
        // Move to the next index in our result array if the
        // next sum puts us over our expected average amount
        if (result[resultIndex] > 0 &&
            result[resultIndex] + item > idealValue &&
            resultIndex < result.Length - 1)
            resultIndex++;

        result[resultIndex] += item;
    }

    // Try to determine if the calculated results can be averaged better 
    var resultsOver = result.Where(item => item > idealValue).ToList();
    var resultsUnder = result.Except(resultsOver).ToList();
    if (resultsUnder.Max() - resultsUnder.Min() > resultsUnder.Count)
    {
        // Recalculate idealValue again based on the final results
        // by getting the sum of the difference of the items that are over
        // and dividing it by the total number of items
        idealValue += resultsOver.Select(item => item - idealValue).Sum() / result.Length;

        // Reset our results
        result = new int[resultCount];
        resultIndex = 0;

        foreach (var item in input)
        {
            // Move to the next index in our result array if the
            // next sum puts us over our expected average amount
            if (result[resultIndex] > 0 &&
                result[resultIndex] + item > idealValue &&
                resultIndex < result.Length - 1)
                resultIndex++;

            result[resultIndex] += item;
        }
    }

    return result;
}

所以现在当我们使用输入 {80, 99, 60, 200, 50, 70, 90} 时，在我们计算第一个结果集 ({179, 60, 410}) 之后，我们重新计算 idealValue结束了，获取平均值，并将其添加到我们的 idealValue，例如：410 - 216 = 194, 194 / 3 = 64, idealValue = 216 + 64 = 280。然后我们重置结果并再次运行它，最后是：

{239, 250, 160}

在不重新排列的情况下将数组拆分为大约相等的总和

Splitting array into about equals sums without rearranging

c#

arrays

split

sum

equals