Membuang orang-orang paling gemuk keluar dari pesawat yang kelebihan muatan.

Katakanlah Anda punya pesawat terbang, dan bahan bakarnya rendah. Kecuali jika pesawat menurunkan berat penumpang 3.000 pon, itu tidak akan dapat mencapai bandara berikutnya. Untuk menyelamatkan jumlah maksimum nyawa, kami ingin membuang orang-orang terberat dari pesawat terlebih dahulu.

Dan oh ya, ada jutaan orang di pesawat, dan kami ingin algoritma yang optimal untuk menemukan penumpang terberat, tanpa harus menyortir seluruh daftar.

Ini adalah masalah proxy untuk sesuatu yang saya coba kode dalam C ++. Saya ingin melakukan "partial_sort" pada manifes penumpang berdasarkan berat, tetapi saya tidak tahu berapa banyak elemen yang akan saya butuhkan. Saya dapat mengimplementasikan algoritma "partial_sort" saya sendiri ("partial_sort_accumulate_until"), tapi saya ingin tahu apakah ada cara yang lebih mudah untuk melakukan ini menggunakan STL standar.

Salah satu caranya adalah menggunakan min heap ( std::priority_queuedalam C ++). Begini cara Anda melakukannya, dengan asumsi Anda memiliki MinHeapkelas. (Ya, contoh saya adalah dalam C #. Saya pikir Anda mendapatkan ide.)

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.

Menurut referensi standar, waktu berjalan harus sebanding dengan n log k, di mana njumlah penumpang dank jumlah maksimum barang di heap. Jika kita mengasumsikan bahwa berat penumpang biasanya 100 lbs atau lebih, maka tidak mungkin bahwa tumpukan akan mengandung lebih dari 30 item setiap saat.

Kasus terburuk adalah jika penumpang disajikan dalam urutan dari berat terendah ke tertinggi. Itu akan mengharuskan setiap penumpang ditambahkan ke heap, dan setiap penumpang dikeluarkan dari heap. Namun, dengan satu juta penumpang dan dengan asumsi bahwa yang paling ringan berbobot 100 lbs, makan log k berhasil sedikit.

Jika Anda mendapatkan bobot penumpang secara acak, kinerjanya jauh lebih baik. Saya menggunakan sesuatu yang seperti ini untuk mesin rekomendasi (saya memilih 200 item teratas dari daftar beberapa juta). Saya biasanya berakhir dengan hanya 50.000 atau 70.000 item yang benar-benar ditambahkan ke heap.

Saya menduga Anda akan melihat sesuatu yang sangat mirip: mayoritas kandidat Anda akan ditolak karena mereka lebih ringan daripada orang yang paling ringan yang ada di tumpukan. Dan PeekmerupakanO(1) operasi.

Untuk informasi lebih lanjut tentang kinerja tumpukan pilih dan pilih cepat, lihat Ketika teori bertemu praktik . Versi singkat: jika Anda memilih kurang dari 1% dari jumlah total item, maka heap pilih adalah pemenang yang jelas atas pemilihan cepat. Lebih dari 1%, lalu gunakan pilih cepat atau varian seperti Introselect .

Namun, ini tidak akan membantu untuk masalah proxy Anda:

Untuk 1.000.000 penumpang untuk menurunkan berat 3000 pon, setiap penumpang harus kehilangan (3000/1000000) = 0,003 lbs per orang. Itu bisa dicapai dengan membuang setiap baju, atau sepatu, atau bahkan mungkin kliping kuku, menyelamatkan semua orang. Ini mengasumsikan pengumpulan dan pembuangan yang efisien sebelum penurunan berat yang dibutuhkan meningkat karena pesawat menggunakan lebih banyak bahan bakar.

Sebenarnya, mereka tidak mengizinkan gunting kuku di papan lagi, jadi itu keluar.

Di bawah ini adalah implementasi sederhana dari solusi langsung. Saya tidak berpikir ada cara yang lebih cepat yaitu 100% benar.

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());
        }
    }
 }

Ini bekerja dengan mengisi set "orang mati" sampai memenuhi ambang batas. Setelah ambang batas terpenuhi, kami terus menelusuri daftar penumpang yang berusaha menemukan yang lebih berat daripada orang mati paling ringan. Ketika kami telah menemukan satu, kami menambahkan mereka ke daftar dan kemudian mulai "Menyimpan" orang-orang paling ringan dari daftar sampai kami tidak dapat menyimpan lagi.

Dalam kasus terburuk, ini akan melakukan hampir sama dengan semacam seluruh daftar. Tetapi dalam kasus terbaik ("daftar mati" diisi dengan benar dengan orang X pertama) itu akan tampil O(n).

Dengan asumsi semua penumpang akan bekerja sama: Gunakan jaringan penyortiran paralel . (lihat juga ini )

Ini demonstrasi langsung

Perbarui: Video alternatif (lompat ke 1:00)

Meminta pasangan orang untuk membandingkan-pertukaran - Anda tidak bisa lebih cepat dari ini.

@ Blastfurnace berada di jalur yang benar. Anda menggunakan pilihan cepat di mana pivot adalah ambang batas berat. Setiap partisi membagi satu set orang menjadi set, dan mengembalikan bobot total untuk setiap set orang. Anda terus memecahkan ember yang sesuai sampai ember Anda yang sesuai dengan berat tertinggi orang lebih dari 3000 pound, dan ember terendah Anda yang ada di set itu memiliki 1 orang (artinya, tidak dapat dibagi lebih jauh.)

Algoritma ini adalah waktu linier diamortisasi, tetapi kasus terburuk kuadratik. Saya pikir itu adalah satu-satunya algoritma waktu linier .

Berikut adalah solusi Python yang menggambarkan algoritma ini:

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

Keluaran:

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]

Dengan asumsi bahwa, seperti bobot orang, Anda memiliki ide bagus tentang apa nilai maksimum dan minimum yang mungkin akan menggunakan jenis radix untuk mengurutkannya dalam O (n). Maka cukup bekerja dari ujung terberat dari daftar menuju yang paling ringan. Total waktu berjalan: O (n). Sayangnya, tidak ada implementasi semacam radix di STL, tetapi cukup mudah untuk menulis.

Mengapa Anda tidak menggunakan quicksort parsial dengan aturan aborsi yang berbeda dari "diurutkan". Anda dapat menjalankannya dan kemudian menggunakan hanya bagian yang lebih tinggi dan terus sampai berat dalam bagian yang lebih tinggi ini tidak mengandung berat yang setidaknya harus dibuang lagi, daripada Anda kembali satu langkah dalam rekursi dan mengurutkan daftar. Setelah itu Anda dapat mulai mengusir orang-orang dari ujung atas daftar yang diurutkan.

Semacam Turnamen Paralel Massively: -

Dengan asumsi tiga kursi standar setiap sisi ailse: -

1. Mintalah penumpang di kursi dekat untuk pindah ke kursi tengah jika mereka lebih berat daripada orang di kursi dekat.

2. Mintalah penumpang di kursi tengah untuk bertukar dengan penumpang di kursi lorong jika mereka lebih berat.

3. Minta penumpang di kursi lorong kiri untuk bertukar dengan penumpang di kursi kanan, mereka lebih berat.

4. Bubble mengurutkan penumpang di kursi lorong kanan. (Mengambil n langkah untuk n baris). - minta penumpang di kursi lorong kanan untuk bertukar dengan orang di depan dan -1 kali.

5 Tendang mereka hingga mencapai £ 3000.

3 langkah + n langkah ditambah 30 langkah jika Anda memiliki penumpang yang benar-benar kurus.

Untuk pesawat dua lorong - instruksinya lebih kompleks tetapi kinerjanya hampir sama.

Saya mungkin akan menggunakan std::nth_elementuntuk mempartisi 20 orang terberat dalam waktu linier. Kemudian gunakan metode yang lebih kompleks untuk menemukan dan menghantam yang terberat dari yang terberat.

Anda dapat membuat satu melewati daftar untuk mendapatkan rata-rata dan standar deviasi, kemudian menggunakannya untuk memperkirakan jumlah orang yang harus pergi. Gunakan partial_sort untuk menghasilkan daftar berdasarkan nomor itu. Jika tebakannya rendah, gunakan partial_sort lagi pada sisanya dengan tebakan baru.

@James memiliki jawaban di komentar: a std::priority_queuejika Anda dapat menggunakan wadah apa pun, atau kombinasi dari std::make_heapdan std::pop_heap(dan std::push_heap) jika Anda ingin menggunakan sesuatu seperti a std::vector.

Berikut ini adalah solusi berbasis tumpukan menggunakan modul heapq bawaan Python. Itu di Python jadi tidak menjawab pertanyaan asli, tapi itu lebih bersih (IMHO) daripada solusi Python diposting lainnya.

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)

Jika k = jumlah penumpang untuk dilemparkan dan N = jumlah penumpang, maka kasus terbaik untuk algoritma ini adalah O (N) dan kasus terburuk untuk algoritma ini adalah Nlog (N). Kasus terburuk terjadi jika k berada di dekat N untuk waktu yang lama. Berikut adalah contoh pemeran terburuk:

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

Namun, dalam hal ini (membuang orang dari pesawat (dengan parasut, saya kira)) maka k harus kurang dari 3000, yaitu << "jutaan orang". Karena itu, runtime rata-rata seharusnya sekitar Nlog (k), yang linier dengan jumlah orang.