最优再分配算法定理

Question

假设我有一个相同的存储桶(数量为n)，分布在相同的存储桶(数量为m)中。给定的分布可能是公平/均匀的，也可能不是。我们的目标是编写一种算法，通过传输一些项来统一地重新分发这些项。每次传输都有关联的成本，因此传输的数量必须是最小的。

例如，在这个分布中，我在3个存储桶中总共有7个项目。输入是每个存储桶中项目数量的大小为'm‘的向量，其中- 4，2，1

解决方案将涉及从存储桶1到存储桶3的1次转移，结果分布将如下所示- 3，2，2

由于n(7)不能被m(3)完全整除，这是最接近的可实现的均匀分布。

另一个示例案例-输入：{1，4，5，11}

输出：{5，5，5，6}

转到输出的传输次数:5

我正在寻找一些现有的算法来解决这个问题。谢谢!

Answer 1

虽然您的用例不需要在实现中投入太多考虑，因为数字显然很小，但有时可能需要使用时间复杂度基本上不依赖于项目数量的算法，例如：

import numpy as np

def dist(inp):
    inp = np.array(inp)
    m = len(inp)            # number of buckets
    n = sum(inp)            # number of items
    l = n//m                # low number in an output bucket
    h = (n+m-1)//m          # high number in an output bucket
    lo = inp < l            # buckets which need transfer to
    hi = inp > h            # buckets which need transfer from
    out = np.empty(m, int)
    out[lo] = l             # fill underfull buckets with low
    out[hi] = h             # fill overfull buckets with high
    out[~lo & ~hi] = inp[~lo & ~hi] # keep other buckets as is
    o = sum(out)            # check missing or surplus items
    if o < n: out[np.where(out == l)[0][:n-o]] = h  # adjust
    if o > n: out[np.where(out == h)[0][:o-n]] = l  # adjust
    return out