Jeter les gens plus gros hors d’un avion surchargé.

Question

Disons que vous avez un avion, et il est peu de carburant. À moins que l'avion gouttes de 3000 livres de poids des passagers, il ne sera pas en mesure d'atteindre l'aéroport le plus proche. Pour sauver le maximum de vies, nous aimerions jeter le plus lourd de personnes hors de l'avion en premier.

Et oh oui, il y a des millions de personnes dans l'avion, et nous aimerions un algorithme optimal pour trouver le plus lourd des passagers, sans nécessairement le tri de l'ensemble de la liste.

C'est un problème de proxy pour quelque chose que je suis en train de coder en C++. Je voudrais faire un "partial_sort" sur la liste des passagers en poids, mais je ne sais pas combien d'éléments que je vais avoir besoin. J'ai pu mettre en œuvre mes propres "partial_sort" algorithme ("partial_sort_accumulate_until"), mais je me demandais si il ya un moyen plus facile de faire cela en utilisant le standard STL.

Answer 1

Ce n'est pas aider pour votre proxy problème, cependant:

Pour 1 000 000 de passagers à la chute de 3000 livres de poids, chaque passager doit perdre (3000/1000000) = 0.003 kg par personne. Qui pourrait être atteint par le biais de vidange de chaque chemise, des chaussures ou de, ou probablement même des coupures d'ongles, de sauver tout le monde. Cela suppose une collecte efficace et larguer avant de la perte de poids a besoin de davantage que l'avion a consommé plus de carburant.

En fait, ils ne permettent pas de coupe-ongles à bord de plus, jusqu'à ce qui est.

Answer 2

Un autre moyen serait d'utiliser un tas min (std::priority_queue en C++). Voici comment vous pouvez le faire, en supposant que vous avez eu un MinHeap classe. (Oui, mon exemple est en C#. Je pense que vous obtenez l'idée.)

int targetTotal = 3000;
int totalWeight = 0;
// this creates an empty heap!
var myHeap = new MinHeap<Passenger>(/* need comparer here to order by weight */);
foreach (var pass in passengers)
{
    if (totalWeight < targetTotal)
    {
        // unconditionally add this passenger
        myHeap.Add(pass);
        totalWeight += pass.Weight;
    }
    else if (pass.Weight > myHeap.Peek().Weight)
    {
        // If this passenger is heavier than the lightest
        // passenger already on the heap,
        // then remove the lightest passenger and add this one
        var oldPass = myHeap.RemoveFirst();
        totalWeight -= oldPass.Weight;
        myHeap.Add(pass);
        totalWeight += pass.Weight;
    }
}

// At this point, the heaviest people are on the heap,
// but there might be too many of them.
// Remove the lighter people until we have the minimum necessary
while ((totalWeight - myHeap.Peek().Weight) > targetTotal)
{
    var oldPass = myHeap.RemoveFirst();
    totalWeight -= oldPass.Weight; 
}
// The heap now contains the passengers who will be thrown overboard.

Selon cette norme, les références, les temps d'exécution doit être proportionnel n log koù n le nombre de passagers et en k est le nombre maximum d'éléments sur le tas. Si nous supposons que les passagers de poids sera généralement de 100 livres ou plus, il est peu probable que le tas contenir plus de 30 éléments à tout moment.

Le pire, ce serait le cas si les passagers sont présentés dans l'ordre de le poids le plus faible à la plus élevée. Qui exigeraient que chaque passager être ajouté au tas, et chaque passager être retiré dans le tas. Pourtant, avec un million de passagers et en supposant que le plus léger pèse 100 lbs, n log k correspond à un assez petit nombre.

Si vous obtenez les passagers en poids de façon aléatoire, les performances sont bien meilleures. J'utilise quelque chose de tout à fait comme cela pour un moteur de recommandation (je sélectionne le top 200 des éléments à partir d'une liste de plusieurs millions de dollars). Je finissent généralement avec seulement 50 000 à 70 000 éléments réellement ajouté au tas.

Je pense que vous verrez quelque chose de tout à fait similaires: la majorité de vos candidats seront rejetés parce qu'ils sont plus légers que le plus léger de la personne déjà sur le tas. Et Peek est O(1) de l'opération.

Pour plus d'informations sur la performance des tas de sélectionner et de sélection rapide, voir Quand la théorie rencontre la pratique. Version courte: si vous êtes à la sélection des moins de 1% du nombre total d'éléments, tas select est un gagnant clair, plus rapide, sélectionnez. Plus de 1%, puis utilisez sélection rapide ou une variante comme Introselect.

Answer 3

Ci-dessous est assez simple de mise en œuvre de la solution simple et efficace. Je ne pense pas qu'il existe un moyen plus rapide qui est correct à 100%.

size_t total = 0;
std::set<passenger> dead;
for ( auto p : passengers ) {
    if (dead.empty()) {
       dead.insert(p);
       total += p.weight;
       continue;
    }
    if (total < threshold || p.weight > dead.begin()->weight)
    {
        dead.insert(p);
        total += p.weight;
        while (total > threshold)
        {
            if (total - dead.begin()->weight < threshold)
                break;
            total -= dead.begin()->weight;
            dead.erase(dead.begin());
        }
    }
 }

Cela fonctionne en remplissant l'ensemble des "morts" jusqu'à ce qu'il respecte le seuil. Une fois que le seuil est atteint, on continue par le biais de la liste des passagers en essayant de trouver des qui sont plus lourd que le plus léger des morts. Quand nous l'avons trouvé, nous l'ajoutons à la liste et ensuite commencer à "Sauver" le plus léger des personnes de la liste jusqu'à ce que nous ne pouvons pas sauver plus.

Dans le pire des cas, cela permettra de réaliser le même comme une sorte de l'ensemble de la liste. Mais dans le meilleur des cas (les "morts de la liste" est rempli correctement avec le premier X personnes), il effectuera O(n).

Answer 4

En supposant que tous les passagers vont coopérer: Utilisez un réseau de tri parallèle . (voir aussi ceci )

Voici une démonstration en direct

Demander à des paires de personnes de comparer-échanger-vous ne pouvez pas aller plus vite que cela.

Answer 5

@Blastfurnace était sur la bonne voie. Vous utilisez quickselect où les pivots sont un seuil de poids. Chaque partition partage un ensemble de personnes dans les jeux, et renvoie le poids total de chaque ensemble de la population. Vous continuer à informer approprié seau jusqu'à ce que vos compartiments correspondant aux le poids le plus élevé de personnes, plus de 3000 livres, et votre plus bas seau qui est dans le jeu a 1 personne (qui est, il ne peut pas être divisé.)

Cet algorithme est linéaire en temps amorti, mais est quadratique pire des cas. Je pense que c'est le seul temps linéaire de l'algorithme.

---

Voici un Python solution qui illustre cet algorithme:

#!/usr/bin/env python
import math
import numpy as np
import random

OVERWEIGHT = 3000.0
in_trouble = [math.floor(x * 10) / 10
              for x in np.random.standard_gamma(16.0, 100) * 8.0]
dead = []
spared = []

dead_weight = 0.0

while in_trouble:
    m = np.median(list(set(random.sample(in_trouble, min(len(in_trouble), 5)))))
    print("Partitioning with pivot:", m)
    lighter_partition = []
    heavier_partition = []
    heavier_partition_weight = 0.0
    in_trouble_is_indivisible = True
    for p in in_trouble:
        if p < m:
            lighter_partition.append(p)
        else:
            heavier_partition.append(p)
            heavier_partition_weight += p
        if p != m:
            in_trouble_is_indivisible = False
    if heavier_partition_weight + dead_weight >= OVERWEIGHT and not in_trouble_is_indivisible:
        spared += lighter_partition
        in_trouble = heavier_partition
    else:
        dead += heavier_partition
        dead_weight += heavier_partition_weight
        in_trouble = lighter_partition

print("weight of dead people: {}; spared people: {}".format(
    dead_weight, sum(spared)))
print("Dead: ", dead)
print("Spared: ", spared)

Sortie:

Partitioning with pivot: 121.2
Partitioning with pivot: 158.9
Partitioning with pivot: 168.8
Partitioning with pivot: 161.5
Partitioning with pivot: 159.7
Partitioning with pivot: 158.9
weight of dead people: 3051.7; spared people: 9551.7
Dead:  [179.1, 182.5, 179.2, 171.6, 169.9, 179.9, 168.8, 172.2, 169.9, 179.6, 164.4, 164.8, 161.5, 163.1, 165.7, 160.9, 159.7, 158.9]
Spared:  [82.2, 91.9, 94.7, 116.5, 108.2, 78.9, 83.1, 114.6, 87.7, 103.0, 106.0, 102.3, 104.9, 117.0, 96.7, 109.2, 98.0, 108.4, 99.0, 96.8, 90.7, 79.4, 101.7, 119.3, 87.2, 114.7, 90.0, 84.7, 83.5, 84.7, 111.0, 118.1, 112.1, 92.5, 100.9, 114.1, 114.7, 114.1, 113.7, 99.4, 79.3, 100.1, 82.6, 108.9, 103.5, 89.5, 121.8, 156.1, 121.4, 130.3, 157.4, 138.9, 143.0, 145.1, 125.1, 138.5, 143.8, 146.8, 140.1, 136.9, 123.1, 140.2, 153.6, 138.6, 146.5, 143.6, 130.8, 155.7, 128.9, 143.8, 124.0, 134.0, 145.0, 136.0, 121.2, 133.4, 144.0, 126.3, 127.0, 148.3, 144.9, 128.1]