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

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

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

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

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

Ответы

Ответ 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)

То есть, если у вас нет очередей, сумма min равна 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

Ответ 2

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

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

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

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

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