Сплит массив на основе веса куска - PullRequest
Новая
       18

Сплит массив на основе веса куска

0 голосов
/ 30 августа 2018

У меня есть массив с 2 <= n <= 100 doubles: 

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

Я попробовал вероятностный подход:

  • выборка из [1, 2, .., n] с использованием A в качестве весов вероятности

  • разрезать образец на квантили, чтобы найти хорошее разбиение,

но это было недостаточно стабильно для производства.

tl; dr Этот вопрос задает вопрос о делении на 2 части. Мне нужно k -частное деление.

1 Ответ

0 голосов
/ 30 августа 2018

Рассчитать общую сумму массива 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]]
...