如何通过总人数和总价值在工人之间平均分配工作？

Question

我在解决分配问题时遇到问题。

我有工人和工作案例。每个工作用例都有一个值。我需要分配工作案例，以使所有工人得到的总价值相等的案件数量相等（如果可能）。

案例总数和工人总数是随机的。

什么是解决此问题的最佳方法？我完全被困住了。我的第一个想法就是按值对它们进行排序，然后像这样将它们分发出去：

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

这个问题听起来可能很难解决。看一下Knapsack-Problem，这是相似的。如果不限制每个工作人员的案例数，则可以按workCases降序排列value，然后始终将下一个workCase分配给当前负载最低的工作人员。请注意，即使是这种算法也不一定能产生最佳结果。

您可以尝试的另一种方法是，首先为每个工人分配正确的随机作业数量，然后废除找到负载最低和负载最高的工人，然后让他们从负载轻，负载轻的工人那里调换繁重的工作工作量很大的工人的工作。请注意，此解决方案也仅是一种启发式方法，可能无法产生最佳结果。

但是同样，这个问题似乎没有快速完美的解决方案，尝试找到一个NP难题，并将其简化为您的问题，以表明它不能解决（现在适合您。）>

Answer 2

正如Morinator已经解决的那样，这是背包问题的一个变体，没有完美的解决方案（除了纯粹的蛮力和合适的数字之外）。