[解決済み】過積載の飛行機から一番太っている人を放り出す。

質問

例えば、ある飛行機が燃料不足になったとします。 乗客の体重3000ポンドを落とさない限り、飛行機は次の空港に到着することができない。 最大限の人命を救うために、体重の重い人を先に飛行機から投げ捨てたいと思います。

そうそう、飛行機には何百万人もの人が乗っているので、必ずしもリスト全体をソートすることなく、最も重い乗客を見つける最適なアルゴリズムが欲しいのです。

これは、私がC++でコーディングしようとしているものの代理問題です。 私は乗客名簿を重量で部分的にソートしたいのですが、必要な要素の数がわかりません。 私自身の "partial_sort" アルゴリズム ("partial_sort_accumulate_until") を実装することができますが、標準 STL を使用してこれを行う簡単な方法があるかどうか疑問に思っています。

どのように解決するのですか？

一つの方法として ミニヒープ ( 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件を選択する）。実際にヒープに追加されるアイテムは、通常5万から7万個程度です。

ヒープ上の最も軽い人よりも軽いので、候補者の大半が却下されるのです。そして Peek は O(1) 演算を行う。

ヒープセレクトとクイックセレクトの性能について詳しくは 理論と実践が出会うとき . 簡単に説明すると、選択する項目が全体の1%未満であれば、ヒープ選択がクイック選択より明らかに勝っています。1%以上であれば、クイック選択か、以下のようなバリエーションを使用します。 イントロセレクト .