将值均匀分配到容器中的算法？ [英] Algorithm to evenly distribute values into containers?

问题描述

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

Does anyone know a way to evenly distribute numbers into a set number of containers, making sure that the total values of the containers are as even as possible?

编辑：尽可能是指每个容器的总数（如果分配到X个容器中）将接近平均总数。

by "even as possible" I mean that the total of each container will be as close to the total average if distributed in X amount of containers.

现在，我简单地对数字数组进行排序（降序），然后将其值（不考虑其值）分布到容器中。将1000个，200个，20个，1000个分配到三个容器中的集合等于[2000]，[200]，[20]。

Right now I simply sort the array of numbers(descending) and then distribute them, oblivious of their value, into the containers. A set of 1000, 200, 20, 1000 distributed into three containers would equal [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.

但是我不知道用整齐的方式在代码中表达这一点。

But I do not know of a neat way to express this in code.

想法？

推荐答案

您是否拥有大型数据集，且对象，以及您必须找到最佳解决方案的铸铁要求？如果是这样的话，这是不现实的。

Do you have a large dataset, with much variance in the size of objects, and a cast iron requirement that you must find the very best solution? If so, this is not realistic.

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

But the good news is that many problems that are NP-complete in theory, are quite easy in the real world! If your number of datapoints is relatively small, then you can probably do an intelligent (but still thorough) search and find the globally optimum solution.

此外， if如果您有一个行为良好的数据集，则值的差异会很小，您可能会很快发现一个完全均匀地填充所有容器的解决方案。如果是这样，那么这显然是最好的答案。即使在非常大的数据集上，这也可以很好地工作。 （我认为您想要的是一个具有许多小值的数据集，这些数据集可用于最终整理事物。）。

Also, if the variance in the values is quite small if you have a nicely behaved dataset, you might quickly stumble across a solution that fills all the containers exactly evenly. If so, then this is obviously the best possible answer. This could work well even on very large datasets. (I think that what you want here is a dataset with lots of small values that can be used to easily tidy things up at the end.).

所以，不要不要放弃！首先，对数据进行排序，并考虑从最大到最小的数据点。在每个阶段，将下一个值分配给当前最小的容器。

So, don't give up! First, sort your data and consider the data points from the largest to the smallest. At each stage, assign the next value to the container which is currently smallest. This probably won't give you the optimal solution in all cases, but it might be quite reasonable in practice.

排序 1000、200、20>



排序 1000、200、20 ，例如1000 ，则会为您提供 1000、1000、200、20 。然后，该算法将为您提供

Sorting 1000, 200, 20, 1000, would give you 1000, 1000, 200, 20. This algorithm would then give you:

1000        = 1000
1000        = 1000
200   +20   =  220

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

This happens to be the optimal solution, but it won't always be the case.

====

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

If you are willing and able to try more complex algorithms, look up the partition problem:

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

Although the partition problem is NP-complete, there is a pseudo-polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "The Easiest Hard Problem".

有一个分区问题的优化版本，可以对多集进行分区将S分为两个子集S1，S2，以使S1中的元素之和与S2中的元素之和之间的差最小。

There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized.

这篇关于将值均匀分配到容器中的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！