12. Greedy

Greedy (serakah) berarti mengambil pilihan yang paling menguntungkan saat ini, lalu tidak pernah mundur. Algoritmanya biasanya pendek dan cepat — sering hanya sort diikuti satu penelusuran. Bahayanya juga di situ: greedy yang salah terlihat sama meyakinkannya dengan greedy yang benar.

Bentuk umum

1. Urutkan data menurut suatu ukuran.
2. Telusuri sekali dari depan.
3. Di setiap langkah, ambil kalau memungkinkan.

Jumlah langkahnya O(n log n) karena sort, jadi greedy cocok untuk soal berbatasan n ≤ 200.000 atau lebih.

Seluruh kesulitan greedy ada di langkah 1: diurutkan menurut apa?

Ukuran pengurutan yang sering dicoba, dan bentuk soal yang biasanya cocok dengannya:

Daftar ini adalah daftar dugaan, bukan daftar jawaban. Setiap dugaan tetap harus diuji, dan bagian akhir bab ini membahas caranya.

Contoh yang berhasil: uang kembalian

Diberikan pecahan uang Indonesia 100.000, 50.000, 20.000, 10.000, 5.000, 2.000, dan 1.000. Berapa lembar paling sedikit untuk membayar k rupiah?

Greedy: ambil sebanyak mungkin dari pecahan terbesar, lalu turun.

int pecahan[] = {100000, 50000, 20000, 10000, 5000, 2000, 1000};

int lembar = 0;
for (int i = 0; i < 7; i++) {
    lembar += k / pecahan[i];
    k %= pecahan[i];
}

Untuk k = 87.000: 87.000 → satu 50.000, sisa 37.000 → satu 20.000, sisa 17.000 → satu 10.000, sisa 7.000 → satu 5.000, sisa 2.000 → satu 2.000. Lima lembar, dan tidak ada cara dengan empat lembar.

Kenapa greedy benar di sini: setiap pecahan uang Indonesia selalu habis dibagi atau "cukup rapat" terhadap pecahan di bawahnya, sehingga mengambil satu lembar besar tidak pernah bisa dikalahkan oleh beberapa lembar kecil. Sifat itu milik daftar pecahannya, bukan milik soal "cari lembar paling sedikit" — dan itulah yang membuat contoh berikutnya gagal.

Contoh yang gagal: pecahan buatan

Ganti pecahannya menjadi 1, 3, dan 4, lalu bayar 6.

• Greedy: ambil 4, sisa 2; ambil 1, sisa 1; ambil 1. Tiga koin.
• Jawaban terbaik: 3 + 3. Dua koin.

Greedy salah. Tidak ada yang bisa diperbaiki dengan menambah aturan kecil; soal seperti ini membutuhkan dynamic programming (Bab 13).

Kalau seluruh nilai 1 sampai 10 diperiksa, kegagalannya ternyata jarang — dan justru itu bahayanya:

Delapan dari sepuluh nilai cocok. Kalau kamu hanya mencoba k = 1 sampai k = 5, greedy terlihat benar sempurna. Inilah sebabnya greedy tidak boleh "diuji sekilas": yang diperlukan adalah pemeriksaan menyeluruh atas data kecil, bukan dua tiga contoh yang kebetulan terpikir.

Contoh klasik: penjadwalan kegiatan

Ada n kegiatan, masing-masing dengan waktu mulai s[i] dan waktu selesai f[i]. Kamu hanya bisa mengikuti satu kegiatan pada satu waktu. Berapa kegiatan terbanyak yang bisa diikuti?

Tiga ukuran pengurutan yang terlihat masuk akal:

Alasan yang benar: kegiatan yang selesai paling awal menyisakan waktu terbanyak bagi kegiatan berikutnya. Setiap penyelesaian lain bisa ditukar kegiatan pertamanya dengan kegiatan yang selesai paling awal tanpa membuat jawabannya lebih buruk.

Kedua ukuran yang salah punya contoh penyangkal yang sangat kecil:

• Waktu mulai paling awal. Kegiatan (0–10), (1–2), (3–4). Greedy mengambil (0–10) dan berhenti di situ: 1 kegiatan. Jawaban terbaik (1–2) dan (3–4): 2 kegiatan.
• Durasi terpendek. Kegiatan (1–5), (4–6), (5–9). Greedy mengambil (4–6) yang berdurasi 2, dan keduanya yang lain jadi bertabrakan: 1 kegiatan. Jawaban terbaik (1–5) dan (5–9): 2 kegiatan.

Menelusuri greedy yang benar pada enam kegiatan (1–4), (3–5), (0–6), (5–7), (3–8), (8–10) — sudah terurut menurut waktu selesai:

Jawabannya 3 kegiatan. Perhatikan kegiatan ke-3 yang paling panjang (0–6): meskipun ia mulai paling awal, mengambilnya justru akan menghalangi dua kegiatan lain.

sort(keg, keg + n, [](Kegiatan a, Kegiatan b) {
    return a.selesai < b.selesai;
});

int banyak = 0;
int waktu = -1000000000;          // kapan kegiatan terakhir selesai
for (int i = 0; i < n; i++) {
    if (keg[i].mulai >= waktu) {
        banyak++;
        waktu = keg[i].selesai;
    }
}

Bentuk [](...) { return ...; } adalah lambda: fungsi kecil tanpa nama yang diberikan kepada sort sebagai aturan pengurutan. Untuk buku ini, cukup kenali polanya — kembalikan true kalau a harus berada sebelum b.

struct Kegiatan {
    int mulai, selesai;
};
Kegiatan keg[100005];

Contoh: muatan perahu

n orang menunggu menyeberang. Berat orang ke-i adalah b[i]. Setiap perahu memuat paling banyak dua orang dan total berat paling banyak k. Berapa perahu paling sedikit?

Greedy yang benar: urutkan berat, lalu pasangkan yang paling ringan dengan yang paling berat. Kalau keduanya muat, berangkatkan berdua; kalau tidak, yang terberat berangkat sendiri.

sort(b, b + n);

int kiri = 0, kanan = n - 1, perahu = 0;
while (kiri <= kanan) {
    if (b[kiri] + b[kanan] <= k) kiri++;   // yang ringan ikut
    kanan--;                               // yang berat selalu berangkat
    perahu++;
}

Menelusuri untuk berat 1 2 3 4 5 dan k = 6:

Tiga perahu: {1, 5}, {2, 4}, dan {3} sendiri.

Alasan greedy ini benar: orang terberat pasti berangkat, itu tidak bisa dihindari. Pertanyaannya hanya apakah ia bisa ditemani. Kalau yang paling ringan pun tidak muat bersamanya, tidak ada seorang pun yang muat, jadi ia berangkat sendiri. Kalau yang paling ringan muat, memasangkannya tidak pernah merugikan — orang ringan itu paling mudah dipasangkan dengan siapa pun, jadi "menyimpannya" untuk nanti tidak memberi keuntungan.

Pola "dua penunjuk dari ujung berlawanan" ini muncul di banyak soal greedy.

Cara meyakinkan diri bahwa greedy benar

Tiga cara, dari yang paling cepat sampai yang paling meyakinkan:

1. Cari contoh penyangkal. Coba data kecil yang aneh: dua elemen sama, satu elemen sangat besar, semua elemen sama. Satu contoh yang gagal sudah cukup untuk membuang rencana itu.
2. Uji dengan pembanding. Tulis brute force yang mencoba semua kemungkinan untuk n ≤ 8, lalu bandingkan pada ribuan data acak (Bab 10). Ini cara paling praktis saat lomba.
3. Argumen penukaran. Tunjukkan bahwa jawaban terbaik mana pun bisa diubah sedikit demi sedikit menjadi jawaban greedy tanpa memperburuknya. Inilah pembuktian sungguhan, dan itulah yang dilakukan pada penjadwalan kegiatan di atas.

Pekerjaan rumah

Kesalahan yang paling sering

Tips OSN

Greedy hampir selalu berarti "urutkan dulu". Pertanyaan sesungguhnya bukan "apakah ini greedy", melainkan "diurutkan menurut apa". Empat urutan di bawah menutupi sebagian besar soal greedy di tingkat awal:

Yakinkan diri dengan argumen penukaran. Bentuknya selalu sama: andaikan ada jawaban terbaik yang urutannya berbeda dari pilihan greedy; tukar dua bagian yang berdekatan; tunjukkan hasilnya tidak menjadi lebih buruk. Kalau penukaran itu selalu bisa dilakukan, pilihan greedy pasti termasuk salah satu jawaban terbaik. Argumen sependek itu sudah cukup untuk membedakan greedy yang benar dari greedy yang kebetulan lolos contoh.

Uji greedy dengan brute force sebelum mengirim. Untuk N ≤ 10, jawaban brute force pasti benar. Jalankan keduanya pada ratusan masukan acak kecil dan bandingkan dengan diff. Greedy yang salah biasanya gugur pada masukan acak kelima atau keenam — jauh sebelum kamu kehilangan waktu di ruang lomba.

Kalau greedy gagal, biasanya soalnya DP. Ciri yang sering muncul: pilihan sekarang mempengaruhi pilihan yang tersedia nanti dengan cara yang tidak bisa diringkas menjadi satu angka. Bab 13 membahas penggantinya.

Perhatikan perbedaan "sebanyak mungkin" dan "sebesar mungkin". Memilih kegiatan terbanyak diurutkan menurut waktu selesai; memilih kegiatan dengan total nilai terbesar tidak bisa greedy dan memang soal DP. Satu kata pada soal mengubah seluruh pendekatannya.

Jangan mengurutkan data yang urutannya bagian dari soal. Kalau jawaban menuntut nomor urut aslinya, simpan nomor itu bersama datanya sebelum mengurutkan — misalnya sebagai pair. Kehilangan nomor asli adalah kesalahan yang baru ketahuan setelah seluruh kode selesai.

Ringkasan

• Greedy mengambil pilihan terbaik saat ini dan tidak pernah mundur; bentuk bakunya sort lalu satu penelusuran, O(n log n).
• Seluruh kesulitannya ada pada satu pertanyaan: diurutkan menurut apa.
• Greedy yang benar untuk satu kumpulan data bisa salah untuk kumpulan data lain — kebenarannya milik datanya, bukan bentuk soalnya.
• Tiga cara memeriksanya: cari contoh penyangkal kecil, uji dengan pembanding brute force pada ribuan data acak, dan argumen penukaran.
• Contoh baku yang perlu dikenali: uang kembalian, penjadwalan kegiatan (urut menurut waktu selesai), dan muatan perahu (dua penunjuk dari ujung berlawanan).
• Kalau greedy terbukti salah dan tidak ada ukuran pengurutan lain yang bertahan, yang dibutuhkan adalah dynamic programming di Bab 13.

Latihan bergaya OSN

Ketiganya diselesaikan dengan satu kali pengurutan disusul satu kali baca. Yang menentukan benar-salahnya adalah apa yang dijadikan kunci urut, jadi tuliskan dulu argumen penukarannya sebelum mengetik.

Kerangka ketiganya ada di exercises/12/osn/.

Soal 1 — Antrian Layanan

Sebuah loket hanya bisa melayani satu orang pada satu waktu. Pagi itu N pelanggan sudah hadir semua sejak loket dibuka, dan pelanggan ke-i memerlukan Tᵢ menit untuk dilayani. Petugas boleh memanggil pelanggan dalam urutan mana pun.

Waktu tunggu seorang pelanggan adalah lamanya ia menunggu sejak loket dibuka sampai giliran layanannya dimulai — tidak termasuk lama layanannya sendiri. Tentukan total waktu tunggu terkecil yang bisa dicapai.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat T₁ T₂ … T_N.

Format keluaran. Satu baris berisi total waktu tunggu terkecil.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ Tᵢ ≤ 10.000

Contoh masukan

3
5 1 3

Contoh keluaran

5

Penjelasan. Urutan terbaik adalah 1, 3, 5. Pelanggan pertama menunggu 0 menit, pelanggan kedua 1 menit, pelanggan ketiga 1 + 3 = 4 menit. Totalnya 5. Urutan 5, 3, 1 memberi total 0 + 5 + 8 = 13.

Kerangkanya: exercises/12/osn/01-antrian-layanan.cpp

Soal 2 — Titik Pemeriksaan

Sepanjang sebuah jalan lurus terdapat N ruas yang harus diawasi. Ruas ke-i membentang dari kilometer Lᵢ sampai kilometer Rᵢ, termasuk kedua ujungnya.

Panitia akan mendirikan pos pemeriksaan pada titik-titik kilometer bulat. Sebuah ruas dianggap terawasi kalau ada sedikitnya satu pos yang berdiri di dalam ruas itu. Tentukan banyaknya pos paling sedikit yang diperlukan agar semua ruas terawasi.

Format masukan. Baris pertama berisi bilangan bulat N. N baris berikutnya masing-masing berisi dua bilangan bulat Lᵢ dan Rᵢ.

Format keluaran. Satu baris berisi banyaknya pos paling sedikit.

Batasan.

• 1 ≤ N ≤ 200.000
• 1 ≤ Lᵢ ≤ Rᵢ ≤ 10⁹

Contoh masukan

4
1 3
2 5
4 7
6 9

Contoh keluaran

2

Penjelasan. Satu pos di kilometer 3 mengawasi ruas pertama dan kedua. Satu pos lagi di kilometer 7 mengawasi ruas ketiga dan keempat. Dua pos tidak bisa dikurangi lagi, karena ruas pertama dan ruas keempat tidak punya kilometer yang sama.

Kerangkanya: exercises/12/osn/02-titik-pemeriksaan.cpp

Soal 3 — Pasangan Beban

Ada 2N barang yang harus diangkut dengan N gerobak. Setiap gerobak memuat tepat dua barang. Beban sebuah gerobak adalah jumlah berat kedua barang di dalamnya.

Panitia ingin gerobak yang paling berat sekecil mungkin. Tentukan beban gerobak terberat pada susunan terbaik.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi 2N bilangan bulat, berat setiap barang.

Format keluaran. Satu baris berisi beban gerobak terberat yang paling kecil.

Batasan.

• 1 ≤ N ≤ 100.000
• 1 ≤ berat ≤ 10⁹

Contoh masukan

3
3 5 2 8 1 4

Contoh keluaran

9

Penjelasan. Susunan terbaik memasangkan 1 dengan 8 (beban 9), 2 dengan 5 (beban 7), dan 3 dengan 4 (beban 7). Gerobak terberatnya 9. Susunan lain seperti (8, 5), (4, 3), (2, 1) menghasilkan gerobak terberat 13.

Kerangkanya: exercises/12/osn/03-pasangan-beban.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.