Разделить список на подмножества - PullRequest
Новая
       65

Разделить список на подмножества

3 голосов
/ 21 декабря 2011

У меня есть список элементов, которые я хотел бы разделить на подмножества. Ради обсуждения допустим, что это файлы. Я хотел бы, чтобы каждое подмножество содержало не более 5 файлов, и чтобы общий размер файлов в подмножестве был менее 1 МБ, если это возможно. Если один файл превышает 1 МБ, он должен быть в подмножестве сам по себе.

Я записал это в несколько более обобщенной форме, используя общий размер элемента вместо размера файла. Но я подозреваю, что есть более простой и / или лучший способ сделать это. Какие-либо предложения?

Вот что у меня есть: 

public static IEnumerable<IEnumerable<T>> InSetsOf<T>(this IEnumerable<T> source, int maxItemsPerSet, int maxMetricPerSet, Func<T, int> getMetric)
{
    int currentMetricSum = 0;
    List<T> currentSet = new List<T>();

    foreach (T listItem in source)
    {
        int itemMetric = getMetric(listItem);

        if (currentSet.Count > 0 && 
            (currentSet.Count >= maxItemsPerSet || (currentMetricSum + itemMetric) > maxMetricPerSet))
        {
            yield return currentSet;

            //Start a new subset
            currentSet = new List<T>();
            currentMetricSum = 0;
        }

        currentSet.Add(listItem);
        currentMetricSum += itemMetric;
    }

    //Return the last set
    yield return currentSet;
}

Ответы [ 2 ]

2 голосов
/ 21 декабря 2011

Упаковка в бункер - сложная задача для NP.Единственный способ получить оптимальное решение - это протестировать все комбинации.Если имеется фиксированное количество различных размеров, это может быть систематически выполнено с использованием динамического программирования (для SO есть ответ с примером кода для этого случая), но время выполнения для такого алгоритма ужасно.

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

A Поиск в Google вернул это как один из результатов: Базовый анализэвристики бин-упаковки (есть бумага , которая анализирует результаты).По-видимому, алгоритм наилучшего соответствия с таблицей соответствия бина обеспечивает хорошие результаты при разумном времени выполнения.

0 голосов
/ 21 декабря 2011

Тест на 1 МБ отсутствует, но в противном случае ваш код выглядит нормально для меня. Я не думаю, что есть значительно лучший способ сделать это.

...