最优再分配算法

Question

假设我有一桶相同的物品（n 个）分布在相同的桶（m 个）中。给定的分布可能是也可能不是 fair/uniform。目标是编写一个算法，可以通过转移一些项目来统一重新分配这些项目。每次转账都有相关费用，所以转账次数必须最少。

例如，我在这个分布的 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

虽然您的用例不需要在实施中考虑太多，但由于数字显然很小，有时可能需要使用时间复杂度基本上不依赖于项目数量的算法，e . g.:

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

最优再分配算法

Optimum redistribution algorothm

algorithm

optimization

load-balancing