Алгоритм: Найти минимальную сумму k чисел из n массивов (очередей)

Question

Предположим, что существует n очередей положительных чисел. Мне нужна минимальная сумма k чисел, выбранных из этих очередей. Обратите внимание, что это очереди, поэтому упорядочение важно, и только один номер может быть выбран из любой очереди за раз. Как только это число будет выбрано и удалено из очереди, мы можем перейти к следующей очереди в этой очереди. Поэтому сортировка не допускается (порядок важен).

Например:

Найти минимальную сумму двух чисел

2 12 3 4 
8 2 2 
10 10 

В приведенном выше примере можно выбрать либо 2 из первой очереди и 8 со второго или 8 и 2 и от второго. Оба варианта дают сумму 10.

Пример 2:

Найти минимальную сумму двух чисел

4 15 2 
8 2 2 
10 10 

В приведенном выше примере один должен выбрать 8 и 2 как из второго списка.

Я сначала думал о линии сортировки списков слияния K, но это не сработает. Я могу думать только об одном рабочем подходе. Он должен попробовать все комбинации из всех очередей. Может кто-нибудь предложить лучший способ или направить меня к нему?

Answer 1

Позвольте F(qs, k) быть минимальной суммой из числа k номеров из очередей qs. Тогда:

F([], k) = 0 if k == 0, otherwise +infinity. 
F([q] + qs, k) = min_i(q[0] + q[1] + ... + q[i-1] + F(qs, k-i) for i in 0...k) 

То есть, если у Вас есть никакие очередей не остались, минимальная сумма 0, в противном случае, вы можете взять i номер из первой очереди, и k-i от остальные.

Это можно эффективно решить с помощью динамического программирования, построив таблицу (n, k), где n - количество очередей. В Python 2:

def F(qs, n, k, cache): 
    if k == 0: 
     return 0 
    if n == 0: 
     return 1e12 
    if (n, k) not in cache: 
     best = 1e12 
     s = 0 
     for i in xrange(k+1): 
      if i > len(qs[len(qs)-n]): 
       break 
      if i > 0: 
       s += qs[len(qs)-n][i-1] 
      best = min(best, s + F(qs, n-1, k-i, cache)) 
     cache[n, k] = best 
    return cache[n, k] 

egs = [ 
    (2, [[2, 2, 3, 4], [8, 2, 2], [10, 10]]), 
    (2, [[4, 15, 2], [8, 2, 2], [10, 10]]), 
    (3, [[100, 100, 100], [101, 101, 2]]) 
] 

for k, qs in egs: 
    print k, qs 
    print F(qs, len(qs), k, dict()) 
    print 

распечаток

2 [[2, 2, 3, 4], [8, 2, 2], [10, 10]] 
4 

2 [[4, 15, 2], [8, 2, 2], [10, 10]] 
10 

3 [[100, 100, 100], [101, 101, 2]] 
204 

Answer 2

Сначала попытайтесь решить более простую задачу: Как найти наименьшие K элементов из массива длиной м?

Инициализируйте максимальный размер кучи k из первых k элементов массива (да максимальная куча, а не мини-куча). Перемещайтесь по остальной части массива. На каждом шаге сравните текущий элемент с корнем кучи (это k-й наименьший элемент, увиденный до сих пор). Если текущий элемент меньше, удалите корень кучи и вставьте текущий элемент, соблюдая осторожность при сохранении кучи-инварианта.

Когда сделано, куча содержит наименьшие k элементов из массива. Алгоритм имеет временную сложность O (m log k) и пространственную сложность O (k)

---

Реализация в Python. Python имеет только min-heap module, поэтому эмулируйте максимальную кучу, принимая отрицание всего.

import heapq # min-heap operations 

def sum_smallest_k(queues, k): 
    """Sum the smallest k elements across queues""" 
    heap = [] # maintain a max-heap size k 

    for queue in queues: 
     for x in queue: 
      if len(heap) < k: 
       heapq.heappush(heap, -1 * x) 
      else: 
       heapq.heappushpop(heap, -1 * x) 

    return -1 * sum(heap) 

Ваши примеры

>>> sum_smallest_k([[2, 12, 3, 4], [8, 2, 2], [10, 10]], 2) 
4 
>>> sum_smallest_k([[4, 15, 2], [8, 2, 2], [10, 10]], 2) 
4