Arrojando a la gente más gorda de un avión sobrecargado.

Esto no ayudará para su problema de proxy, sin embargo:

Para que 1,000,000 pasajeros bajen 3000 libras de peso, cada pasajero debe perder (3000/1000000) = 0.003 libras por persona. Eso podría lograrse desechando cada camisa, o zapatos, o probablemente incluso recortes de uñas, salvando a todos. Esto supone una recolección eficiente y el deshecho antes de que la pérdida de peso necesaria aumentara a medida que el avión usaba más combustible.

En realidad, no permiten cortauñas a bordo nunca más, así que eso está fuera.

A continuación se muestra una implementación bastante simple de la solución directa. No creo que haya una forma más rápida que sea 100% correcta.

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());
        }
    }
 }

Esto funciona llenando el conjunto de "personas muertas" hasta que alcanza el umbral. Una vez que se alcanza el umbral, seguimos revisando la lista de pasajeros tratando de encontrar cualquiera que sea más pesado que la persona muerta más ligera. Cuando hemos encontrado uno, los añadimos a la lista y luego comenzamos a "Guardar" a las personas más ligeras de la lista hasta que no podamos guarda más.

En el peor de los casos, esto se llevará a cabo aproximadamente lo mismo que una especie de toda la lista. Pero en el mejor de los casos (la "lista muerta" se llena correctamente con las primeras X personas) funcionará O(n).

Suponiendo que todos los pasajeros cooperarán: red de clasificación paralela. (véase también este )

Aquí hay una demostración en vivo

Actualización: Video alternativo (saltar a 1:00)

Pedir a pares de personas que comparen-intercambien - no puede ser más rápido que esto.

@Blastfurnace estaba en el camino correcto. Utilice quickselect donde los pivotes son umbrales de peso. Cada partición divide un conjunto de personas en conjuntos y devuelve el peso total de cada conjunto de personas. Continúa rompiendo el balde apropiado hasta que sus baldes correspondientes a las personas de mayor peso superen las 3000 libras, y su balde más bajo que está en ese conjunto tenga 1 persona (es decir, no se puede dividir más.)

Este algoritmo es tiempo lineal amortizado, pero el peor caso cuadrático. Creo que es el único algoritmo de tiempo lineal.

Aquí hay una solución de Python que ilustra este algoritmo:

#!/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)

Salida:

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]

Suponiendo que, al igual que los pesos de las personas, usted tiene una buena idea de lo que los valores máximo y mínimo son probables utilizar un tipo radix para ordenarlos en O(n). A continuación, simplemente trabajar desde el extremo más pesado de la lista hacia el más ligero. Tiempo total de funcionamiento: O (n). Desafortunadamente, no hay una implementación de una ordenación radix en el STL, pero es bastante sencillo de escribir.

¿Por qué no usa un quicksort parcial con una regla de aborto diferente a "ordenado"? Puede ejecutarlo y luego usar solo la mitad superior y continuar hasta que el peso dentro de esta mitad superior no contenga el peso que al menos debe desecharse más, luego retroceda un paso en la recursión y clasifique la lista. Después de que usted puede comenzar a tirar a la gente de la parte superior de esa lista ordenada.

Clasificación Masiva de Torneos Paralelos: -

Suponiendo un estándar de tres asientos a cada lado de la ailse: -

1. Pida a los pasajeros en el asiento de la ventana que se muevan al asiento del medio si pesan más que la persona en el asiento de la ventana.

2. Pida a los pasajeros en el asiento del medio que intercambien con el pasajero en el asiento del pasillo si son más pesados.

3. Pídale al pasajero en el asiento del pasillo izquierdo que intercambie con el pasajero en el asiento del pasillo derecho más pesado.

4. Burbuja ordenar a los pasajeros en el asiento del pasillo derecho. (Toma n pasos para n filas). -- pida a los pasajeros en el asiento del pasillo derecho que intercambien con la persona en frente n -1 veces.

5 Patéalos por la puerta hasta que alcances 3000 libras.

3 pasos + n pasos más 30 pasos si tienes una carga de pasajeros realmente delgada.

Para un avión de dos pasillos the las instrucciones son más complejas pero el rendimiento es más o menos el mismo.

Probablemente usaría std::nth_element para dividir las 20 personas más pesadas en tiempo lineal. Luego use un método más complejo para encontrar y eliminar el más pesado de los pesados.

Usted podría hacer una pasada sobre la lista para obtener la media y la desviación estándar, a continuación, utilizar que para aproximar el número de personas que tienen que ir. Utilice partial_sort para generar la lista basada en ese número. Si la conjetura fue baja, use partial_sort de nuevo en el resto con una nueva conjetura.

@James tiene la respuesta en los comentarios: un std::priority_queue si usted puede utilizar cualquier recipiente, o una combinación de std::make_heap y std::pop_heap (y std::push_heap) si quieres usar algo como un std::vector.

Aquí hay una solución basada en heap usando el módulo heapq integrado en Python. Está en Python, por lo que no responde a la pregunta original, pero es más limpio (en mi humilde opinión) que la otra solución de Python publicada.

import itertools, heapq

# Test data
from collections import namedtuple

Passenger = namedtuple("Passenger", "name seat weight")

passengers = [Passenger(*p) for p in (
    ("Alpha", "1A", 200),
    ("Bravo", "2B", 800),
    ("Charlie", "3C", 400),
    ("Delta", "4A", 300),
    ("Echo", "5B", 100),
    ("Foxtrot", "6F", 100),
    ("Golf", "7E", 200),
    ("Hotel", "8D", 250),
    ("India", "8D", 250),
    ("Juliet", "9D", 450),
    ("Kilo", "10D", 125),
    ("Lima", "11E", 110),
    )]

# Find the heaviest passengers, so long as their
# total weight does not exceeed 3000

to_toss = []
total_weight = 0.0

for passenger in passengers:
    weight = passenger.weight
    total_weight += weight
    heapq.heappush(to_toss, (weight, passenger))

    while total_weight - to_toss[0][0] >= 3000:
        weight, repreived_passenger = heapq.heappop(to_toss)
        total_weight -= weight


if total_weight < 3000:
    # Not enough people!
    raise Exception("We're all going to die!")

# List the ones to toss. (Order doesn't matter.)

print "We can get rid of", total_weight, "pounds"
for weight, passenger in to_toss:
    print "Toss {p.name!r} in seat {p.seat} (weighs {p.weight} pounds)".format(p=passenger)

Si k = el número de pasajeros a lanzar y N = el número de pasajeros, entonces el mejor caso para este algoritmo es O(N) y el peor caso para este algoritmo es Nlog(N). El peor caso ocurre si k está cerca de N durante mucho tiempo. He aquí un ejemplo del peor reparto:

weights = [2500] + [1/(2**n+0.0) for n in range(100000)] + [3000]

Sin embargo, en este caso (tirar a la gente del avión (con un paracaídas, supongo)) entonces k debe ser menos de 3000, que es