把最胖的人从一架超载的飞机上抛下。

假设你有一架飞机,而且燃油很低。 除非飞机降低了3000磅的乘客重量,否则将无法到达下一个机场。 为了节省最多的生命,我们首先要把最重的人从飞机上抛下。

噢,飞机上有数百万人,我们希望有一个最佳的algorithm来find最重的乘客,而不必对整个列表进行sorting

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

12 Solutions collect form web for “把最胖的人从一架超载的飞机上抛下。”

一种方法是使用最小堆 (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个物品。

最糟糕的情况是,如果乘客按照从最低重量到最高重量的顺序排列。 这就要求每一个乘客都要join堆中,每个乘客都要从堆中取出。 尽pipe如此,拥有一百万乘客,并假设最轻的重量为100磅,但是这个数量还是相当小的。

如果随机获得乘客的体重,性能会更好。 我用推荐引擎(我从几百万列表中select前200个项目)的东西。 通常情况下,实际上只有50,000或70,000个物品添加到堆中。

我怀疑你会看到一些非常相似的东西:大多数候选人会被拒绝,因为他们比已经在堆上的最轻的人轻。 PeekO(1)操作。

有关堆select和快速select的更多信息,请参阅理论遇到实践时 。 简短版本:如果您select的项目总数less于1%,那么堆select明显胜过快速select。 超过1%,然后使用快速select或类似Introselect的变体。

但是这对于您的代理问题将无济于事。

为了让1,000,000名乘客降低3000磅的重量,每名乘客必须损失(3000/1000000)= 0.003磅/人。 这可以通过抛弃每一件衬衫或鞋子,甚至可能是指甲剪报来实现,从而挽救所有人。 这假设有效的收集和抛弃之前需要增加的重量损失,因为飞机使用更多的燃料。

事实上,他们不允许在船上的指甲刀,所以已经出来了。

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

这是通过填补一套“死人”,直到达到门槛。 一旦达到这个门槛,我们就会继续浏览那些试图find比最轻的死者更重的乘客名单。 当我们find一个,我们将它们添加到列表中,然后开始“拯救”最轻的人,直到我们不能再保存。

在最糟糕的情况下,这将执行大致相同的整个列表。 但在最好的情况下(“死亡名单”用第一个X人正确填写),它将执行O(n)

假设所有乘客都会合作:使用并行分拣networking 。 (也见这个 )

这是一个现场演示

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

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

@Blastfurnace在正确的轨道上。 您使用quickselect枢轴是重量阈值。 每个分区将一组人分成组,并返回每组人的总重量。 你继续打破适当的斗,直到你的水桶相当于最高的重量的人超过3000磅,而你最低的桶是1人(也就是说,它不能再分裂)。

这个algorithm是线性时间分摊的,但是是二次最坏的情况。 我认为这是唯一的线性时间algorithm


下面是一个说明这个algorithm的Python解决scheme:

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

假设像人们的权重一样,你可以很好地理解最大值和最小值可能是用什么样的基数sorting在O(n)中sorting的。 然后简单地从列表最重的一端向最轻的那一端工作。 总运行时间:O(n)。 不幸的是,在STL中没有实现一个基数sorting,但是写起来非常简单。

为什么不使用具有不同于“sorting”的中止规则的部分快速sorting。 你可以运行它,然后使用更高的一半,继续下去,直到在这个更高的一半内的重量不包含至less要被抛出的重量,比你在recursion中返回一步并对列表进行sorting。 之后,您可以开始从sorting列表的高端抛出人员。

大型平行锦标赛sorting: –

假设一个标准的三个座位的每一边: –

  1. 如果坐在靠窗的座位上的乘客比坐在靠窗的座位上的人重,则要求坐在靠窗的座位上的乘客移动到中间的座位上。

  2. 要求中间座位的乘客在靠近过道的位置与乘客交换。

  3. 要求左侧过道座位上的乘客与右侧过道座位上的乘客交换重量。

  4. 泡沫将乘客分配在右侧过道的座位上。 (n行n步)。 – 要求右边通道的乘客与前面的人交换n次-1。

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

3步+ n步加30步,如果你有一个真正瘦客运负荷。

对于两个过道的飞机 – 说明比较复杂,但性能差不多。

我可能会使用std::nth_element在线性时间内分割出20个最重的人。 然后用一个更复杂的方法find最重的重物。

你可以通过列表中的一个来获得均值和标准差,然后用它来近似需要去的人数。 使用partial_sort生成基于该号码的列表。 如果猜测较低,则用新的猜测再次使用partial_sort。

@James在注释中有答案:一个std::priority_queue如果你可以使用任何容器,或者std::make_heapstd::pop_heap (和std::push_heap )的组合,如果你想使用类似std::vector

这是一个使用Python内buildheapq模块的基于堆的解决scheme。 它是用Python编写的,所以不能回答原来的问题,但比其他Python解决scheme更清晰(恕我直言)。

 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 =乘客人数,则该algorithm的最佳情况是O(N),该algorithm的最坏情况是Nlog(N)。 如果k长时间接近N,则会发生最坏的情况。 这是一个最糟糕演员的例子:

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

然而,在这种情况下(把人们从飞机上扔下去(我猜想有降落伞)),那么k必须小于3000,这就是“数百万人”。 因此,平均运行时间应该大约为Nlog(k),这与人数是线性的。

  • 为什么我不能做一个引用向量?
  • 如何设置std :: vector的初始大小?
  • vector <bool>的替代方法
  • 我应该避免哪些C ++陷阱?
  • STLangular色特征有​​什么意义?
  • std :: make_pair与std :: pair的构造函数的目的是什么?
  • STL地图 - >按价值sorting?
  • 如果在从开始到结束的迭代过程中调用地图元素上的erase()会发生什么?