Алгоритм балансирования предметов разных размеров в грубо сбалансированных наборах

Question

Я ищу алгоритм, чтобы разбить список элементов разного размера на число групп одинакового размера "N".

В частности, я работаю над сайтом ASP.NET в C #, гдеУ меня есть (из базы данных) список строк.Струны имеют различную длину.У меня есть набор столбцов, которые должны отображать строки.Мне нужен алгоритм, который найдет наиболее сбалансированные наборы (порядок элементов не имеет значения), чтобы последние столбцы были максимально сбалансированы.

Абстрактный пример:

Создание 3 столбцов.

Вещи для распространения:

 - Item A - height 5
 - Item B - height 3
 - Item C - height 7
 - Item D - height 2
 - Item E - height 3

Желаемый результат:

Column 1: Item A, Item D
Column 2: Item C
Column 3: Item B, Item E

Answer 1

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

Answer 2

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

        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;
    }

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

        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).Возможно я выложу другую версию на.