Сбрасывать самых перегруженных людей с перегруженного самолета.

Question

Допустим, у вас есть самолет, и у него мало топлива. Если самолет не сбросит 3000 фунтов веса пассажира, он не сможет добраться до следующего аэропорта. Чтобы сохранить максимальное количество жизней, мы хотели бы сначала сбросить с самолета самых тяжелых людей.

И о, да, в самолете миллионы людей, и мы хотели бы найти оптимальный алгоритм поиска самых тяжелых пассажиров без необходимости сортировки всего списка.

Это проблема с прокси для чего-то, что я пытаюсь кодировать на C ++. Я хотел бы сделать «part_sort» для пассажирского манифеста по весу, но я не знаю, сколько элементов мне понадобится. Я мог бы реализовать свой собственный алгоритм "partal_Sort "(" Partrial_Sort_accumulate_until "), но мне интересно, есть ли какой-нибудь более простой способ сделать это с использованием стандартного STL.

Answer 1

Вы можете сделать один проход по списку, чтобы получить среднее значение и стандартное отклонение, а затем использовать это для приблизительного числа людей, которые должны идти.Используйте part_sort для создания списка на основе этого числа.Если предположение было низким, снова используйте part_sort для остатка с новым предположением.

Answer 2

Вот решение на основе кучи, использующее встроенный в Python модуль heapq. Он написан на Python, поэтому не отвечает на первоначальный вопрос, но он чище (IMHO), чем другое опубликованное решение Python.

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)

Если k = количество брошенных пассажиров, а N = количество пассажиров, то лучшим вариантом для этого алгоритма является O (N), а наихудшим случаем для этого алгоритма является Nlog (N). Наихудший случай возникает, если k находится вблизи N в течение длительного времени. Вот пример худшего состава:

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

Однако в этом случае (выбрасывая людей из самолета (я полагаю, с парашютом)) тогда k должно быть меньше 3000, что составляет << «миллионы людей». Следовательно, среднее время выполнения должно быть около Nlog (k), которое линейно по отношению к количеству людей. </p>