12

有谁知道一种将数字平均分配到一组容器中的方法，以确保容器的总值尽可能均匀？

编辑：“尽可能均匀”是指如果分布在 X 个容器中，每个容器的总数将尽可能接近总平均值。

现在，我只是简单地对数字数组进行排序（降序），然后将它们分配到容器中，忽略它们的值。一组 1000、200、20、1000 分布到三个容器中将等于 [2000]、[200]、[20]。

我想做的是：

Example

Set of numbers: 10 30 503 23 1 85 355
If I were to distribute these into three containers I would just pick the highest first and then distribute them as I go, like this:
Cont 1 = 503
Cont 2 = 355
Cont 3 = 85 + 30 + 23 + 10 + 1

This will give the best possible distribution that you can get with the values provided.

但我不知道用代码表达这一点的巧妙方法。

想法？

4

2 回答 2

3

您是否有一个大型数据集，对象的大小差异很大，并且您必须找到最佳解决方案的铸铁要求？如果是这样，这是不现实的。

但好消息是，许多理论上 NP 完全的问题，在现实世界中都很容易！如果您的数据点数量相对较少，那么您可能可以进行智能（但仍然彻底）搜索并找到全局最优解。

此外，如果你有一个表现良好的数据集，值的差异非常小，你可能很快就会发现一个完全均匀地填充所有容器的解决方案。如果是这样，那么这显然是最好的答案。即使在非常大的数据集上，这也可以很好地工作。（我认为你在这里想要的是一个包含许多小值的数据集，可以用来在最后轻松整理。）。

所以，不要放弃！首先，对数据进行排序，并从最大到最小考虑数据点。在每个阶段，将下一个值分配给当前最小的容器。这可能不会在所有情况下为您提供最佳解决方案，但在实践中可能非常合理。

排序1000, 200, 20, 1000，会给你1000, 1000, 200, 20。然后，该算法将为您提供：

1000        = 1000
1000        = 1000
200   +20   =  220

这恰好是最佳解决方案，但并非总是如此。

====

如果您愿意并且能够尝试更复杂的算法，请查看分区问题：

尽管分区问题是 NP 完全的，但有一个伪多项式时间动态规划解决方案，并且在许多情况下，有一些启发式算法可以优化或近似地解决该问题。因此，它被称为“最简单的难题”。

划分问题有一个优化版本，即将多重集 S 划分为两个子集 S1、S2，使得 S1 中的元素之和与 S2 中的元素之和之间的差异最小化。

于 2013-10-05T13:29:01.030 回答
1

有趣的。到目前为止，这个 C 程序似乎给出了预期的结果。它首先对数据进行排序，然后对于n 个容器，立即将n 个最高的数字存储在每个容器中。（实际上，您可以省略该步骤。）然后，从最大剩余数字到最小，它找到添加该数字与最佳平均值产生最小差异的容器。因为这是从高到低，每个数字都被放入最佳容器中——所有其他数字都较低，因此它们的差异甚至会更大。

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

int sort_numeric (const void *a, const void *b)
{
    return *((int *)a) - *((int *)b);
}

int main (int argc, char **argv)
{
    int list[] = { 10, 30, 503, 23, 1, 85, 355 };
    int i,j, nnumber, ncontainer, total, avgPerContainer, nextError, smallestError, containerForSmallest;
    int *containers, *errors;

    ncontainer = 3;

    nnumber = sizeof(list)/sizeof(list[0]);

    qsort (list, nnumber, sizeof(list[0]), sort_numeric);

    containers = (int *)malloc(ncontainer * sizeof(int));
    for (i=0; i<ncontainer; i++)
        containers[i] = 0;

    errors = (int *)malloc(ncontainer * sizeof(int));
    for (i=0; i<ncontainer; i++)
        errors[i] = 0;


    printf ("input:");
    for (i=0; i<nnumber; i++)
    {
        printf (" %d", list[i]);
    }
    printf ("\n");

//  how much is to be in each container?
    total = 0;
    for (i=0; i<nnumber; i++)
        total += list[i];

//  this will result in a fraction:
//      avgPerContainer = total/ncontainer;
//  so instead we'll use 'total' and *keeping in mind*
//  that the number needs to be divided by ncontainer
    avgPerContainer = total;

    printf ("per container: ~%d\n", (2*avgPerContainer+ncontainer)/(2*ncontainer) );

//  start by putting highest values into each container
    for (i=0; i<ncontainer; i++)
        containers[i] += list[nnumber-ncontainer+i];
//  .. remove from list ..
    nnumber -= ncontainer;

//  print current totals
    for (i=0; i<ncontainer; i++)
    {
        errors[i] = containers[i]*ncontainer - avgPerContainer;
        printf ("#%d: %d, error = %d/%d ~ %+d\n", i, containers[i], errors[i], ncontainer, (2*errors[i]+ncontainer)/(2*ncontainer) );
    }

    printf ("remaining:");
    for (i=0; i<nnumber; i++)
    {
        printf (" %d", list[i]);
    }
    printf ("\n");

//  add the remainders
    for (i=nnumber-1; i>=0; i--)
    {
        smallestError = INT_MAX;
        containerForSmallest = 0;
        for (j=0; j<ncontainer; j++)
        {
            nextError = (containers[j] + list[i]) - avgPerContainer;
            if (nextError < smallestError)
            {
                containerForSmallest = j;
                smallestError = nextError;
                printf ("error for %d, %d + %d, is %+d\n", j, containers[j], list[i], smallestError);
            }
        }
        printf ("we put %d into #%d\n", list[i], containerForSmallest);
        containers[containerForSmallest] += list[i];
    }

    for (i=0; i<ncontainer; i++)
    {
        printf ("#%d: %d, error = %d/%d ~ %+d\n", i, containers[i], containers[i]*ncontainer - avgPerContainer, ncontainer, (2*(containers[i]*ncontainer - avgPerContainer)+ncontainer)/(2*ncontainer) );
    }

    return 0;
}
于 2013-10-05T14:08:57.373 回答