Алгоритм балансировки элементов переменного размера в примерно сбалансированные наборы

Самое быстрое, что можно сделать, это, вероятно, просто вставить каждый новый элемент в наименьший список (где «наименьший» — это сумма размеров всех элементов в списке).

Это похоже на вариант проблемы с упаковочными коробками (или бинарной упаковкой), когда вы пытаетесь разместить коллекцию предметов переменного размера в как можно меньшем количестве контейнеров:

http://en.wikipedia.org/wiki/Bin_packing_problem

В зависимости от размера вашего набора элементов вы, вероятно, могли бы довольно просто подобрать решение, ища комбинацию с наименьшей разницей между размерами. Для больших наборов это становится довольно сложной проблемой, и вам может быть лучше с «простым» алгоритмом, который приблизит вас к хорошему ответу.

Взгляните на алгоритмы планирования вакансий, где у нас есть несколько вакансий разного размера, которые нужно выполнить. распределены по машинам, так что общее время производства минимально.

Вот другая версия, которая может создавать группы нужной длины.

        public static List<List<int>> Balance(List<int> input, int desiredLimit)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(input);
            values.Sort();

            var start = 0;
            var end = values.Count - 1;
            var orderedValues = new List<int>(values.Count);
            while (start < end)
            {
                orderedValues.Add(values[start]);
                orderedValues.Add(values[end]);
                start++;
                end--;
            }
            if (values.Count % 2 != 0)
            {
                orderedValues.Add(values[values.Count / 2]);
            }

            var total = 0;
            var line = new List<int>();

            for (int i = 0; i < orderedValues.Count; i++)
            {
                var v = orderedValues[i];
                total += v;
                if (total <= desiredLimit)
                {
                    line.Add(v);
                }
                else
                {
                    total = v;
                    result.Add(line);
                    line = new List<int>() { v };
                }
            }
            result.Add(line);
        }

        return result;
    }

Попробуйте что-нибудь очень простое

        public static List<List<int>> Balance(List<int> input)
    {
        var result = new List<List<int>>();

        if (input.Count > 0)
        {
            var values = new List<int>(input);

            values.Sort();

            var max = values.Max();
            var maxIndex = values.FindIndex(v => v == max);
            for (int i = maxIndex; i < values.Count; i++)
            {
                result.Add(new List<int> { max });
            }
            var limit = maxIndex;
            for (int i = 0; i < limit / 2; i++)
            {
                result.Add(new List<int> { values[i], values[(limit - 1) - i] });
            }
            if (limit % 2 != 0)
            {
                result.Add(new List<int> { values[limit / 2] });
            }
        }

        return result;
    }

Этот метод можно использовать, если вам нужно сгруппировать по двум элементам. Вы можете изменить его, чтобы группировать элементы, пока не будет достигнуто предопределенное значение (например, 10). Вероятно, я выложу другую версию.

Если у вас есть два столбца, это звучит как приложение проблемы с разделами. Проблема является NP-полной, но есть решение динамического программирования, работающее за псевдополиномиальное время. http://en.wikipedia.org/wiki/Partition_problem

Если вы увеличите количество столбцов больше двух, то решения с псевдополиномиальным временем не будет. http://en.wikipedia.org/wiki/3-partition_problem

Вот общий код, реализующий принятый ответ:

• просто вставляйте каждый новый элемент в наименьший список

• сначала отсортируйте предметы (от большого к меньшему), это значительно улучшит

    class Item { internal Item(int weight) { Weight = weight; } internal int Weight { get; } }
  
    [Test]
    public void Test1() {
  
       var A = new Item(5);
       var B = new Item(3);
       var C = new Item(7);
       var D = new Item(2);
       var E = new Item(3);
  
       Item[][] result = AlgoToBuildBalancedPartition.Go(new[] { A, B, C, D, E }, t => t.Weight, 3);
       Assert.AreEqual(result.Length, 3);
       Assert.Contains(C, result[0]);
       Assert.Contains(A, result[1]);
       Assert.Contains(D, result[1]);
       Assert.Contains(B, result[2]);
       Assert.Contains(E, result[2]);
    }
  
    //--------------------------------------------------
  
    public static class AlgoToBuildBalancedPartition {
  
       public static T[][] Go<T>(
              IEnumerable<T> seq,
              Func<T, int> getWeightProc,
              int maxNbPartitions) where T : class {
          Debug.Assert(!seq.IsNullOrEmpty());
          Debug.Assert(getWeightProc != null);
          Debug.Assert(maxNbPartitions >= 2);
  
          var partitions = new List<Partition<T>>(maxNbPartitions);
  
          T[] seqDescending = seq.OrderByDescending(getWeightProc).ToArray();
          int count = seqDescending.Length;
  
          for (var i = 0; i < count; i++) {
             T item = seqDescending[i];
             if (partitions.Count < maxNbPartitions) {
                partitions.Add(new Partition<T>(item, getWeightProc));
                continue;
             }
  
             // Get partition with smallest weight
             Debug.Assert(partitions.Count == maxNbPartitions);
             var partitionWithMinWeight = partitions[0];
             for (var j = 1; j < maxNbPartitions; j++) {
                var partition = partitions[j];
                if (partition.TotalWeight > partitionWithMinWeight.TotalWeight) { continue; }
                partitionWithMinWeight = partition;
             }
  
             partitionWithMinWeight.AddItem(item);
          }
  
          return partitions.Select(p => p.Items.ToArray()).ToArray();
       }
  
  
       private sealed class Partition<T> where T : class {
          internal Partition(T firstItem, Func<T, int> getWeightProc) {
             Debug.Assert(firstItem != null);
             Debug.Assert(getWeightProc != null);
             m_GetWeightProc = getWeightProc;
             AddItem(firstItem);
          }
          private readonly Func<T, int> m_GetWeightProc;
          internal List<T> Items { get; } = new List<T>();
          internal void AddItem(T item) {
             Debug.Assert(item != null);
             Items.Add(item);
             TotalWeight += m_GetWeightProc(item);
          }
          internal int TotalWeight { get; private set; } = 0;
       }
    }