c - 平衡工作负载分配？

Question

我有 N 份工作，工作量各不相同，需要将其分配给 n 个人，以便工作量尽可能平衡。

例如-我们必须根据工作量划分 5 个工作 <1,2,3,4,5> 3人之间。最好的方法显然是按如下方式分发:-

<1,4>,<2,3>,<5>.

因此问题是最小化

z=abs(a-b)+abs(b-c)+abs(c-a)

哪里a , b , c是三个人的工作量。解决问题最有效的方法是什么？

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *insort(int *var, int elem)
{   // insert elem into sorted variable array var[1..n] (*var holds n)
    int n = var ? *var : 0;
    var = realloc(var, (1 + ++n) * sizeof *var);
    if (!var) exit(1);
    *var = n;
    int i;
    for (i = 1; i < n; ++i) if (elem < var[i]) break;
    memmove(var+i+1, var+i, (n-i) * sizeof *var);
    var[i] = elem;
    return var;
}

main()
{   // distribute jobs characterized by workloads among n persons
    int n, i, j, *jobs = NULL;
    printf("number of persons? "); scanf("%d", &n);
    printf("job workloads? ");
    while (scanf("%d", &i) > 0) jobs = insort(jobs, i);
    int *w, *work[n], load[n];
    for (i = 0; i < n; ++i) work[i] = NULL, load[i] = 0;
    if (n > 0 && jobs) do
    {   // assign the most strenuous job to the least busy person
        w = insort(work[0], j = jobs[(*jobs)--]);
        j += load[0];
        for (i = 1; i < n; ++i) if (load[i] > j) break;
        memmove(load, load+1, --i * sizeof *load), load[i] = j;
        memmove(work, work+1,   i * sizeof *work), work[i] = w;
    } while (*jobs);
    for (i = 0; i < n; ++i, puts(""))
        if (w = work[i]) do printf(" %d", w[(*w)--]); while (*w);
}

示例运行:

number of persons? 3
job workloads? 1 2 3 4 5.
 5
 3 2
 4 1