Question Algorithme: Trouver la somme minimale de k nombres à partir de n tableaux (files d'attente)


Supposons qu'il y ait n files de nombres positifs. J'ai besoin de la somme minimum de k numéros sélectionnés à partir de ces files d'attente. Notez que ce sont des files d'attente et que le classement est important et que seul le premier numéro peut être sélectionné dans n'importe quelle file d'attente à la fois. Une fois ce nombre sélectionné et retiré de la file d'attente, nous pouvons passer à la suivante dans cette file. Le tri n'est donc pas autorisé (l'ordre est important).

Par exemple:

Trouver la somme minimum de deux nombres

2 12 3 4 
8 2 2
10 10

Dans l'exemple ci-dessus, je peux choisir 2 de la première file et 8 de la deuxième ou 8 et 2 de la seconde. Les deux choix donnent une somme de 10.

Exemple 2:

Trouver la somme minimum de deux nombres

4 15 2
8 2 2
10 10

Dans l'exemple ci-dessus, il faut choisir 8 et 2 à la fois dans la deuxième liste.

Je pensais pour la première fois à la liste des listes de fusion, mais cela ne fonctionnera pas. Je ne peux que penser à une approche de travail pour cela. C'est pour essayer toutes les combinaisons de toutes les files d'attente. Est-ce que quelqu'un peut suggérer une meilleure façon ou me guider vers elle?


10
2018-01-11 05:36


origine


Réponses:


Laisser F(qs, k) être la somme minimum de choisir k numéros des files d'attente qs. Alors:

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)

Autrement dit, si vous n’avez plus de file d’attente, la somme minimale est 0, sinon vous pouvez prendre i les numéros de la première file d'attente, et k-i du reste

Cela peut être résolu efficacement en utilisant la programmation dynamique en construisant une table de (n, k) où n est le nombre de files d'attente. En 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

Des tirages

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

13
2018-01-11 06:13



Essayez d'abord de résoudre un problème plus simple: comment trouver les plus petits éléments k à partir d'une longueur de tableau m?

Initialise une taille max-heap k à partir des premiers k éléments du tableau (oui max-heap plutôt que min-heap). Boucle sur le reste du tableau. À chaque étape, comparez l'élément actuel à la racine du tas (c'est le kième plus petit élément vu jusqu'à présent). Si l'élément en cours est plus petit, supprimez la racine du segment de mémoire et insérez l'élément en cours, en veillant à conserver l'invariant de segment de mémoire.

Une fois terminé, le tas contient les k plus petits éléments du tableau. L'algorithme a la complexité temporelle O (m log k) et la complexité de l'espace O (k)


Implémentation en Python. Python n'a qu'un module min-tas, émulez donc un max-heap en prenant le négatif de tout.

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)

Vos exemples

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

0
2018-01-11 10:45