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

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

这个问题听起来像是 NP-hard。看Knapsack-Problem，也差不多。如果您不限制每个工作人员的案例数量，您可以按 value 降序排列 workCases，然后始终将下一个 workCase 分配给当前负载最低的工作人员.请注意，即使是此算法也不一定会产生最佳结果。

您可以尝试的另一件事是首先为每个工人分配正确数量的随机工作，然后重复找到负载最低和最高的工人，让他们从负载低的工人那里交换繁重的工作和大负荷工人的轻松工作。
请注意，此解决方案只是一种启发式方法，可能不会产生最佳结果。

但同样，这个问题似乎没有快速完美的解决方案，尝试找到一个 NP-hard 问题并将其简化为您的问题以表明它不可解决（现在对您而言）。

Answer 2

正如 Morinator 已经解决的那样，这是背包问题的一个变体，不存在完美的解决方案（除了纯粹的暴力破解和幸运地拥有完美匹配的数字）。

但你可以相当接近。请务必注意，较大的案例不如较小的案例灵活。举一个真实世界的例子，如果我想让你精确地填充一个给定的容器，用沙子比用鹅卵石甚至石头更容易。

这个真实世界的例子实际上在这里有很大帮助。如果您想在装满容器的同时最大化 rock/sand 口粮（即尽可能多的石头），您首先要用石头填充容器，然后用沙子填充空隙。

您可以在此处使用您已经尝试过的完全相同的方法：首先分配最大的案例，最后分配最小的案例。但是，您的代码存在错误，因为您重复分配最大的案例而不是继续下一个案例。

因为您有多个工作人员，所以有一个次要考虑因素：尽可能将大型案例分配给他们。最简单的方法是始终将一个案例分配给当前工作负荷最低的工人（在平局的情况下，选择谁并不重要，只需选择第一个并列的工人）。

正在修复您的代码：

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

这并不总能为您提供具有完全匹配的案例负载的完美解决方案，但它是一个合理的近似值。有一些边缘示例的结果不是最佳的，但这种情况很少见。
为了避免这些边缘情况，您的代码的复杂性将不得不 急剧地 增加。在大多数情况下，成本得不偿失。

请注意，这不是最高性能的解决方案，因为它涉及许多集合迭代。但是假设 合理的 数量的工人和工作量（假设在一家公司内作为一个界限），考虑到今天的硬件，这应该不是问题。可以通过手动跟踪每个工作人员的总案例负载来完成一些优化，大致如下：

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

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

它不是那么干净（它需要您手动处理值并始终保持完美同步），但它确实避免了每次都必须迭代每个工作人员的分配案例。

有趣的是，在处理开始时不知道完整的案例列表（这意味着您无法对案例进行排序）的情况下，该系统也能正常工作。只要您将下一个案例分配给负载最低的人，它就会保持类似的公平游戏。

如果您的最后几个案例过大，您最终可能会得到一个不太完美的解决方案。这样想：你已经保持了平衡，然后必须分配一个更大的案例。这总是会引起问题。

但是如果你不能提前知道案例列表，那么你就不能指望对它们进行排序，然后你会得到一个不太完美但仍然合理平衡的结果。

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

How to distribute work equally among workers by total count and total value?

c#

algorithm

mathematical-optimization