Как распределить работу поровну между работниками по общему количеству и общей стоимости?

Question

У меня проблема с решением проблемы распространения.

У меня есть рабочие и рабочие чемоданы. Каждый workCase имеет значение. Мне нужно распределить workCases так, чтобы все работники получали одинаковое количество дел с одинаковой общей стоимостью (если это возможно).

Количество общих дел и работников является случайным.

Какой лучший способ решить это? Я полностью застрял. Моя первая идея состояла в том, чтобы просто упорядочить их по значению и просто выдать их так:

public class WorkCase
{
    public decimal Value { get; set; }
}

public class Worker
{
    public List<WorkCase> Cases { get; set; }
}

public static void Sort(List<WorkCase> cases, List<Worker> workers)
{
    cases = cases.OrderByDescending(c => c.Value).ToList();

    var wCount = workers.Count;

    int i = 0;

    while (cases.Any())
    {
        workers[i].Cases.Add(cases.First());

        if (i == workers.Count - 1)
           i = 0;
        else
           i++;
    }
}

Но это не совсем справедливо по отношению к последнему работнику. Спасибо за помощь.

Answer 1

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

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

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

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

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

Исправление вашего кода:

public static void Sort(List<WorkCase> cases, List<Worker> workers)
{
    cases = cases.OrderByDescending(c => c.Value).ToList();

    foreach(var case in cases)
    {
       // Find the worker with the lowest case load

       var workersByCaseLoad = workers.OrderBy(w => w.Cases.Sum(c => c.Value);
       var workerWithLowestCaseLoad = workersByCaseLoad.First();

       // Assign this case to that worker

       workerWithLowestCaseLoad.Cases.Add(case);
    }
}

Это не всегда net идеальное решение с точно подобранными нагрузками, но это разумное приближение. Есть несколько незначительных примеров, когда результат не оптимален, но эти случаи редки.
Чтобы избежать этих незначительных случаев, сложность вашего кода должна была бы резко возрасти. В большинстве случаев стоимость не стоит выгоды.

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

var workersByCaseLoad = workers.OrderBy(w => w.TotalCaseLoad);
var workerWithLowestCaseLoad = workersByCaseLoad.First();

workerWithLowestCaseLoad.Cases.Add(case);
workerWithLostCaseLoad.TotalCaseLoad += case.Value;

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

---

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

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

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

Answer 2

Эта проблема звучит так, как будто она может быть NP-трудной. Посмотрите на проблему Рюкзак , которая похожа. Если вы не ограничены количеством дел для каждого работника, вы можете отсортировать workCases по убыванию value, а затем всегда назначать следующий workCase работнику с самой низкой текущей нагрузкой. Обратите внимание, что даже этот алгоритм не обязательно дает оптимальный результат.

Еще одна вещь, которую вы можете попробовать, - начать с назначения каждому работнику правильного числа случайных заданий, а затем повторно найти работников с самым низким и максимальная нагрузка и позволяет им менять тяжелую работу у работника с низкой нагрузкой и легкую работу у работника с большой нагрузкой.
Обратите внимание, что это решение также является только heuristi c, который может не дать оптимальных результатов.

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