把最胖的人从超载的飞机上扔下去。

假设你有一架飞机，燃料不足。除非这架飞机的乘客重量减轻3000磅，否则它将无法抵达下一个机场。为了挽救最多的生命，我们想先把最重的人扔出飞机。

哦，是的，飞机上有数百万人，我们想要一个最优算法来找出最重的乘客，而不必对整个列表进行排序。

这是我试图用c++编写代码的代理问题。我想按重量对旅客舱单进行“部分排序”，但我不知道需要多少元素。我可以实现我自己的“partial_sort”算法(“partial_sort_accumulate_until”)，但我想知道是否有任何更简单的方法来使用标准的STL来做到这一点。

13198 次浏览
小开
最佳答案

一种方法是使用最小堆 (c++中的std::priority_queue)。下面是你如何做到这一点，假设你有一个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万名乘客，假设最轻的重量为100磅，n log k计算出来的数字还是相当小的。

如果你随机得到乘客的体重，表现会好得多。我在推荐引擎中使用类似的东西(我从数百万个列表中选择前200个项目)。最后，我通常只向堆中添加了5万或7万项。

我猜你会看到类似的情况:你的大多数候选人会被拒绝，因为他们比已经在堆里的最轻的人要轻。而Peek是一个O(1)操作。

有关堆选择和快速选择性能的更多信息，请参见理论与实践的结合。简而言之:如果你选择的项目少于总数的1%，那么堆选择明显优于快速选择。大于1%，则使用快速选择或类似Introselect的变体。

小开

你可以通过一遍列表来得到平均值和标准差，然后用它们来估计必须离开的人数。使用partial_sort根据该数字生成列表。如果猜测值很低，则对余数再次使用partial_sort，并进行新的猜测。

小开
为什么你不使用一个与“sorted”不同的终止规则的部分快速排序。 你可以运行它，然后只使用上面的那一半直到上面的那一半的权值不再包含至少要被丢弃的那个权值，然后你再回到递归的一步，对列表进行排序。在此之后，你可以开始将人从排序列表的高端抛出
小开

假设所有乘客都愿意合作:使用并行排序网络。(另见这)

这是一个现场演示

更新:选择视频(跳转到1:00)

让两组人来比较-交换-没有比这更快的方法了。

小开

下面是直接解决方案的一个相当简单的实现。我不认为有更快的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)。

小开

@James在评论中给出了答案:如果你可以使用任何容器，则使用std::priority_queue;如果你想使用std::vector之类的容器，则使用std::make_heap和std::pop_heap(以及std::push_heap)的组合。

小开

假设，像人的权重一样，你有一个很好的想法，最大和最小的值可能是什么，使用基数排序，以O(n)排序。然后简单地从最重的一端向最轻的一端开始。总运行时间:O(n)。不幸的是，在STL中没有一个基数排序的实现，但是写起来很简单。

小开

我可能会用std::nth_element在线性时间内划分出20个最重的人。然后用一种更复杂的方法找到并撞掉最重的。

小开

@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]
小开

大规模平行比赛排序:-

假设一个标准的三个座位的两边:-

  1. 如果靠窗座位的乘客比靠窗座位的乘客重，请他们移到中间的座位。

  2. 如果中间座位的乘客较重，请他们与过道座位的乘客交换座位。

  3. 如果他们比较重，请坐在左边过道座位的乘客和坐在右边过道座位的乘客交换一下。

  4. 冒泡排序乘客在右边靠过道的座位。(n步n行)。 ——让坐在靠过道右边座位的乘客与前面的乘客交换n -1次。

5把他们踢出门，直到你达到3000磅。

3步+ n步加上30步如果你的乘客非常少的话。

对于双通道飞机来说，指令更复杂，但性能基本相同。

小开

然而，这对你的代理问题没有帮助:

100万名乘客要减掉3000磅体重，每位乘客必须减掉(3000/1000000)= 0.003磅。这可以通过扔掉每个人的衬衫、鞋子，甚至是剪下来的指甲来实现，拯救每个人。这是假设在飞机消耗更多燃料之前，有效的收集和丢弃需要增加的重量。

事实上，飞机上不允许用指甲刀了，所以这是不允许的。

小开

下面是一个使用Python内置heapq模块的基于堆的解决方案。它是Python的，所以没有回答最初的问题，但它比其他发布的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)，它与人数成线性关系。


提交答案