Materi
Algoritma serakah membangun jawaban selangkah demi selangkah, dan di setiap langkah mengambil pilihan yang tampak terbaik saat itu tanpa pernah meninjau ulang. Algoritma seperti ini cepat dan pendek, tetapi hanya benar untuk masalah yang punya sifat pilihan serakah: pilihan terbaik sesaat selalu bisa diperluas menjadi jawaban terbaik keseluruhan. Sifat itu harus dibuktikan, bukan diasumsikan.
Pemilihan kegiatan adalah contoh yang terbukti benar. Dari sekumpulan kegiatan bermulai dan berselesai, pilih sebanyak mungkin yang tidak bertabrakan di satu ruangan. Aturan serakahnya: urutkan menurut waktu selesai, lalu ambil setiap kegiatan yang mulai tidak lebih awal dari selesainya kegiatan terakhir yang diambil. Kegiatan yang selesai paling awal menyisakan waktu paling banyak untuk sisanya. Aturan lain yang tampak masuk akal, seperti mulai paling awal atau durasi paling pendek, punya contoh penyangkal.
Contoh penyangkal adalah satu masukan kecil yang membuat aturan serakah memberi jawaban salah. Uang kembalian dengan pecahan 1, 3, dan 4 untuk jumlah 6: serakah mengambil pecahan terbesar dulu, 4, lalu 1 dan 1, total tiga keping. Jawaban terbaiknya 3 dan 3, dua keping. Satu contoh seperti itu cukup untuk membuktikan aturannya tidak berlaku umum.
rapat = [(9, 12), (10, 11), (11, 13)] # (mulai, selesai), jam
# Mulai paling awal memilih (9, 12) lalu tidak ada yang muat: 1 rapat.
# Selesai paling awal memilih (10, 11) lalu (11, 13): 2 rapat.
