基于块重量的拆分数组 [英] 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]
usingA
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屋!