基于块重量的拆分数组 [英] Split array basing on chunk weight

问题描述

我有一个数组，其中 2是<< = n< = 100 双打：

I have an array with 2 <= n <= 100 doubles:

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

和整数 2< = k< = min（n ，20）。我需要将 A 分为 k 个子数组：

and an integer 2 <= k <= min(n, 20). I need to split A into k subarrays:

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

             ...

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

，使得每个 B 的总和几乎相等（很难给出严格的定义，这意味着-我对一个近似的解决方案感兴趣。

such that the sum in each B is almost equal (it's hard to give a strict definition what this means - I'm interested in an approximate solution).

示例：

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

我尝试了一种概率方法：

I tried a probabilistic approach:

• 使用 A从 [1、2，..，n] 采样作为概率权重

• sample from [1, 2, .., n] using A as probability weights

将样本切成分位数以找到一个好的分区，

cut the sample into quantiles to find a good partition,

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

but this was not stable enough for production.

tl; dr 这问题询问2个块的划分。我需要 k -大块除法。

tl;dr This question asks about 2-chunk divisions. I need k-chunk division.

推荐答案

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

Calculate overall sum of array S. Every chunk sum should be near S / K.

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

Then walk through array, calculating running sum R. When R+A[i+1] - S/K becomes larger than S/K - R, close current chunk and make R=0. Continue with the next chunk.

您也可以补偿累积误差（如果发生），比较 M 带有 M * S / K

You also can compensate accumulating error (if it occurs), comparing overall sum of M chunks with M * S / K

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

Quick-made code for the last approach (not thoroughly checked)

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]]

这篇关于基于块重量的拆分数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！