将最胖的人从超载的飞机上摔下来。

一尘不染

将最胖的人从超载的飞机上摔下来。

algorithm

假设您有一架飞机，而且燃油低。除非飞机掉落3000磅的乘客体重，否则它将无法到达下一个机场。为了最大程度地挽救生命，我们希望首先将最重的人员从飞机上救出。

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

这是我尝试用C ++编写代码的代理问题。我想按重量对旅客舱单进行“ partial_sort”，但我不知道我需要多少个元素。我可以实现自己的“
partial_sort”算法（“ partial_sort_accumulate_until”），但是我想知道是否有使用标准STL进行此操作的简便方法。

阅读 214

2020-07-28

共1个答案

一尘不染

一种方法是使用最小堆（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万乘客，并且假设最轻的乘客体重为100磅，那么n log k工作量就很小。

如果您随机获得乘客的体重，则性能会更好。我在推荐引擎中使用了类似的内容（我从几百万个列表中选择了前200个项目）。我通常最终只将50,000或70,000个项目实际添加到堆中。

我怀疑您会看到非常相似的东西：您的大多数候选人将被拒绝，因为他们比已有的最轻的人轻。并且Peek是一项O(1)操作。

有关堆选择和快速选择的性能的更多信息，请参阅理论与实践相结合。简短版本：如果您选择的项目少于总项目数的1％，那么堆选择显然是快速选择的赢家。超过1％，然后使用快速选择或类似Introselect的变体。

2020-07-28