c# - 负载平衡值到 8 "silos"

Question

我遇到了一个似乎无法解决的问题。这不是那么容易解释，所以我会尽力而为:

我有一个非常大的值数组，我已经排序了:

[ 2, 8, 26, ..., 1456, 1879, ..., 7812, 9614, ..., 20 408, 26 584 ]

我有 8 个容量无限的空“筒仓”(有点像阵列)。

我的目标是用我所有的值(value)观填充这些孤岛，以使它们尽可能平衡。 当我说“平衡”时，我的意思是我希望筒仓中所有值的总和几乎彼此相等。

例如，如果我的 silo 1 的总和为 52 000，而我的 silo 8 的总和为 30 000 那么这就不好了。如果可能的话，我宁愿使用 41 000 和 43 500 之类的东西。

我已经完成了循环，但它似乎不够精确，因为我在筒仓之间发现了相当大的差异。 我也查看了 bin-packing，但它似乎不适合我。

感谢您提供的任何帮助或建议!

Answer 1

优化问题绝非易事，但由于您希望最小化与平均值的偏差，您只需从最高值到最低值迭代您的值，并将其添加到总和最低的筒仓中。这样您就不会在优化上浪费太多时间并且应该(取决于您的值(value)观)获得相对较好的结果。

// Generate some random data
int[] values = new int[1000];

Random r = new Random();

for (int i = 0; i < values.Length; i++)
{
    values[i] = r.Next(1, 30000);
}

// Initialize silos
const int siloCount = 8;
List<int>[] result = new List<int>[siloCount];
for (int i = 0; i < siloCount; i++)
{
    result[i] = new List<int>();
}

int[] sums = new int[siloCount];
int[] indices = Enumerable.Range(0, siloCount).ToArray();

// Iterate all values in descending order
foreach (int value in values.OrderByDescending(i => i).ToList())
{
    // Find silo with lowest sum (or one of them)
    int siloIndex = indices.First(i => sums[i] == sums.Min());

    // Add to collection and sum - so we don't have to call .Sum() every iteration
    sums[siloIndex] += value;
    result[siloIndex].Add(value);
}

Debug.WriteLine(String.Join("\r\n", result.Select(s => s.Sum())));

.Net Fiddle