把最胖的人从超载的飞机上扔下来.

Question

假设你有一架飞机,它的燃油含量很低.除非飞机下降3000磅的乘客重量,否则它将无法到达下一个机场.为了挽救最大数量的生命,我们想先把最重的人从飞机上扔掉.

哦,是的,飞机上有数百万人,我们希望找到最重的乘客的最佳算法,而不必整理整个列表.

这是我试图用C++编写代码的代理问题.我想按重量对乘客舱单做一个"partial_sort",但我不知道我需要多少元素.我可以实现自己的"partial_sort"算法("partial_sort_accumulate_until"),但我想知道是否有更简单的方法来使用标准STL.

Answer 1

但是,这对您的代理问题没有帮助:

对于1,000,000名乘客减重3000磅的重量,每位乘客必须输掉(3000/1000000)=每人0.003磅.这可以通过抛弃每件衬衫或鞋子,或者甚至可能是指甲剪来实现,从而节省每个人.这假设在飞机使用更多燃料之前减重需要增加之前有效收集和抛弃.

实际上,他们不再允许指甲钳在船上了,所以就这样了.

Answer 2

一种方法是使用最小堆(std::priority_queue在C++中).假设你有一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这样的变体.

Answer 3

以下是直接解决方案的一个相当简单的实现.我不认为有一种更快的方法是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());
        }
    }
 }

这可以通过填写"死人"集来实现,直到达到阈值.一旦达到阈值,我们将继续浏览乘客名单,试图找到比最轻的死人重的任何人.当我们找到一个时,我们将它们添加到列表中,然后开始"保存"列表中最轻的人,直到我们无法再保存.

在最坏的情况下,这将执行与整个列表的大致相同的操作.但在最好的情况下("死人名单"与前X人正确填写)它将会执行O(n).

Answer 4

假设所有乘客都合作:使用并行分拣网络.(另见本)

这是现场演示

更新:替代视频(跳转到1:00)

要求一对人进行比较 - 交换 - 你不能比这更快.

Answer 5

@Blastfurnace走在正确的轨道上.您可以使用快速选择,其中枢轴是重量阈值.每个分区将一组人分成几组,并返回每组人的总权重.您继续打破相应的铲斗,直到您的铲斗对应最高重量的人超过3000磅,并且该组中的最低铲斗有1个人(也就是说,它不能再分开.)

该算法是线性时间摊销,但是二次最坏情况.我认为这是唯一的线性时间算法.

这是一个说明此算法的Python解决方案:

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

输出:

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]

Answer 6

假设像人的权重一样,你很清楚最大值和最小值可能使用基数排序来对它们进行O(n)排序.然后简单地从列表最重的一端向最轻的一端工作.总运行时间:O(n).不幸的是,STL中没有基数排序的实现,但写起来非常简单.

Answer 7

为什么不使用具有与"已排序"不同的中止规则的部分快速排序.你可以运行它然后只使用较高的一半继续直到这个较高的一半内的重量不包含至少被抛出的重量,而不是你在递归中返回一步并对列表进行排序.之后,您可以开始从排序列表的高端抛出人员.

Answer 8

大规模并行锦标赛排序: -

假设ailse每侧标准三个座位: -

1. 如果窗户座位上的乘客比靠窗座位的人更重,请让窗户座位上的乘客移动到中间座位.

2. 如果中间座位的乘客较重,请让乘客与过道座位的乘客交换.

3. 要求左侧过道座位上的乘客与右侧过道座椅中的乘客交换它们更重.

4. 气泡将乘客排在正确的过道座位上.(对n行采取n步). - 要求正确过道座位的乘客与前面的人交换n次.

5踢出门,直到你达到3000磅.

3步+ n步加30步,如果你有一个非常瘦的乘客负荷.

对于双通道飞机 - 指令更复杂但性能大致相同.