根据块权重拆分数组

Question

我有一个数组 2 <= n <= 100 双打：

A = [a1, a2, ... , an], ai > 0

和一个整数 2 <= k <= min(n, 20)。我需要将 A 拆分为 k 个子数组：

B1 = [a1,     a2, ... , ap]
B2 = [ap+1, ap+2, ... , aq]

             ...

Bk = [aw+1, aw+2, ... , an]

使得每个 B 的总和 几乎相等 （很难给出严格的定义这是什么意思 - 我对近似解很感兴趣） .

示例：

Input: A = [1, 2, 1, 2, 1], k=2
Output: [[1, 2, 1], [2, 1]] or [[1, 2], [1, 2, 1]]

我尝试了一种概率方法：

使用 A 作为概率权重从 [1, 2, .., n] 抽样
将样本分成分位数以找到一个好的分区，

但这对于生产来说还不够稳定。

tl;dr 这个询问关于 2-chunk 的划分。我需要 k-chunk 划分。

Answer 1

计算数组的总和S。每个块总和应该接近 S / K.

然后遍历数组，计算运行总和R。当 R+A[i+1] - S/K 变得大于 S/K - R 时，关闭当前块并制作 R=0。继续下一个块。

您还可以补偿累积误差（如果发生），将 M 块的总和与 M * S / K

进行比较

最后一种方法的快速代码（未彻底检查）

def chunks(lst, k):
    s = sum(lst)
    sk = s / k
    #sk = max(s / k, max(lst))
    #variant from user2052436 in comments  
    idx = 0
    chunkstart = 0
    r = 0
    res = []
    for m in range(1, k):
        for idx in range(chunkstart, len(lst)):
            km = k -m
            irest = len(lst)-idx
            if((km>=irest) or (2*r+lst[idx]>2*m*sk)) and (idx>chunkstart):
                res.append(lst[chunkstart:idx])
                chunkstart = idx
                break
            r += lst[idx]
    res.append(lst[idx:len(lst)])
    return res

print(chunks([3,1,5,2,8,3,2], 3))
print(chunks([1,1,1,100], 3))

>>>[[3, 1, 5], [2, 8], [3, 2]]
   [[1, 1], [1], [100]]

根据块权重拆分数组

Split array basing on chunk weight

python

algorithm

approximation

python-3.x