오버로드 된 비행기에서 가장 뚱뚱한 사람들을 버림.

오버로드 된 비행기에서 가장 뚱뚱한 사람들을 버림.

---

비행기가 있고 연료가 부족하다고 가정 해 봅시다. 비행기가 승객 무게 3000 파운드를 떨어 뜨리지 않으면 다음 공항에 도착할 수 없습니다. 최대한의 생명을 구하기 위해 가장 무거운 사람들을 먼저 비행기에서 내쫓고 싶습니다.

그렇습니다. 비행기에는 수백만 명의 사람들이 있으며, 전체 목록을 정렬하지 않고도 가장 많은 승객을 찾는 최적의 알고리즘을 원합니다.

이것은 C ++로 코딩하려는 것에 대한 프록시 문제입니다. 승객 매니페스트에 대해 무게 기준으로 "partial_sort"를 수행하고 싶지만 필요한 요소 수를 알 수 없습니다. 내 "partial_sort"알고리즘 ( "partial_sort_accumulate_until")을 구현할 수 있지만 표준 STL을 사용하여이 작업을 수행하는 더 쉬운 방법이 있는지 궁금합니다.

---

한 가지 방법은 사용하는 것입니다 분 힙 ( std::priority_queueC ++에서)를. MinHeap수업 이 있다고 가정하고 수행하는 방법은 다음과 같습니다 . (예, 내 예는 C #에 있습니다. 아이디어가 있다고 생각합니다.)

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.

표준 참조에 따르면, 시간을 실행하기에 비례한다 n log k, 어디에 n승객의 수이고 k힙에있는 항목의 최대 수입니다. 승객의 체중이 일반적으로 100 파운드 이상이라고 가정하면 힙에 언제든지 30 개가 넘는 품목이 포함될 가능성은 없습니다.

가장 낮은 경우는 승객이 가장 낮은 무게에서 가장 높은 순서대로 제시된 경우입니다. 모든 승객을 힙에 추가하고 모든 승객을 힙에서 제거해야합니다. 그럼에도 불구하고 백만 명의 승객이 있으며 가장 가벼운 무게가 100 파운드라고 가정하면 n log k합리적으로 적은 수로 작동합니다.

승객의 체중을 무작위로 얻는다면 성능이 훨씬 좋습니다. 추천 엔진에 대해 이와 비슷한 것을 사용합니다 (수백만 목록에서 상위 200 개의 항목을 선택합니다). 나는 보통 힙에 실제로 50,000 또는 70,000 개의 항목 만 추가합니다.

나는 당신이 아주 비슷한 것을 보게 될 것이라고 생각합니다. 후보자의 대다수는 이미 더미에있는 가장 가벼운 사람보다 가볍기 때문에 거부됩니다. 그리고 Peek입니다 O(1)작업.

힙 선택 및 빠른 선택의 성능에 대한 자세한 정보는 이론이 실습을 충족하는시기를 참조하십시오 . 짧은 버전 : 총 항목 수의 1 % 미만을 선택하는 경우 힙 선택이 빠른 선택보다 확실한 승자입니다. 1 % 이상인 경우 빠른 선택 또는 Introselect 와 같은 변형을 사용하십시오 .

---

그러나 이것은 프록시 문제에 도움이되지 않습니다.

1,000,000 명의 승객이 3000 파운드의 무게를 떨어 뜨리려면 각 승객은 1 인당 (3000/1000000) = 0.003lbs를 잃어야합니다. 모든 셔츠 나 신발을 제압하거나 손톱을 잘라서 모든 사람을 구할 수 있습니다. 이것은 비행기가 더 많은 연료를 사용함에 따라 필요한 중량 손실이 증가하기 전에 효율적인 수집 및 분사를 가정합니다.

Actually, they don't allow fingernail clippers on board anymore, so that's out.

---

Below is a rather simple implementation of the straightforward solution. I don't think there is a faster way that is 100% correct.

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

This works by filling up the set of "dead people" until it meets the threshold. Once the threshold is met, we keep going through the list of passengers trying to find any that are heavier than the lightest dead person. When we have found one, we add them to the list and then start "Saving" the lightest people off the list until we can't save any more.

In the worst case, this will perform about the same as a sort of the entire list. But in the best case (the "dead list" is filled up properly with the first X people) it will perform O(n).

---

Assuming all passengers will cooperate: Use a parallel sorting network. (see also this)

Here is a live demonstration

Update: Alternative video (jump to 1:00)

Asking pairs of people to compare-exchange - you can't get faster than this.

---

@Blastfurnace was on the right track. You use quickselect where the pivots are weight thresholds. Each partition splits one set of people into sets, and returns the total weight for each set of people. You continue breaking the appropriate bucket until your buckets corresponding to the highest weight people are over 3000 pounds, and your lowest bucket that is in that set has 1 person (that is, it can't be split any further.)

This algorithm is linear time amortized, but quadratic worst case. I think it is the only linear time algorithm.

---

Here's a Python solution that illustrates this algorithm:

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

Output:

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]

---

Assuming that, like people's weights, you have a good idea of what the maximum and minimum values are likely to be use a radix sort to sort them in O(n). Then simply work from the heaviest end of the list towards the lightest. Total running time: O(n). Unfortunately, there isn't an implementation of a radix sort in the STL, but it's pretty straightforward to write.

---

Why don't you use a partial quicksort with a different abort rule than "sorted". You can run it and then use just the higher half and go on until the weight within this higher half does not contain the weight that has at least to be thrown out anymore, than you go back one step in the recursion and sort the list. After that you can start throwing people out from the high end of that sorted list.

---

Massively Parallel Tournament Sort:-

Assuming a standard three seats each side of the ailse:-

1. Ask the passengers in the window seat to move to the middle seat if they are heavier than the person in the window seat.

2. Ask the passengers in the middle seat to swap with the passenger in aisle seat if they are heavier.

3. Ask the passenger in the left aisle seat to swap with the passenger in the right aisle seat id they are heavier.

4. Bubble sort the passengers in the right aisle seat. (Takes n steps for n rows). -- ask the passengers in the right aisle seat to swap with the person in front n -1 times.

5 Kick them out the door until you reach 3000 pounds.

3 steps + n steps plus 30 steps if you have a really skinny passenger load.

For a two aisle plane -- the instructions are more complex but the performance is about the same.

---

I would probably use std::nth_element to partition off the 20 heaviest people in linear time. Then use a more complex method to find and bump off the heaviest of the heavies.

---

You could make one pass over the list to get the mean and the standard deviation, then use that to approximate the number of people that have to go. Use partial_sort to generate the list based on that number. If the guess was low, use partial_sort again on the remainder with a new guess.

---

@James has the answer in the comments: a std::priority_queue if you can use any container, or a combination of std::make_heap and std::pop_heap (and std::push_heap) if you want to use something like a std::vector.

---

Here's a heap-based solution using Python's built-in heapq module. It's in Python so doesn't answer the original question, but it's cleaner (IMHO) than the other posted Python solution.

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)

If k = the number of passengers to toss and N = the number of passengers, then the best case for this algorithm is O(N) and the worst case for this algorithm is Nlog(N). The worst case occurs if k is near N for a long time. Here's an example of the worst cast:

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

However, in this case (throwing people off the plane (with a parachute, I presume)) then k must be less than 3000, which is << "millions of people". The average runtime should therefore be about Nlog(k), which is linear to the number of people.

참고URL : https://stackoverflow.com/questions/7746648/throwing-the-fattest-people-off-of-an-overloaded-airplane