My first Magazine pemrograman-kompetitif-dasar | Page 67

6.3 Greedy Choice
sub persoalan
^
a x .start
^
a x .end
Gambar 6.1: Subpersoalan pada activity selection.
Bagaimana caranya menemukan subpersoalan dari activity selection ? Diberikan daftar
kegiatan yang dinomori 1 sampai N. Kita asumsikan daftar ini terurut berdasarkan nilai a i .start.
Asumsikan kegiatan pertama yang kita ikuti adalah kegiatan ke-x. Maka, kegiatan selanjutnya
yang diikuti haruslah memiliki waktu awal ≥ a x .end. Jika j adalah nilai terkecil yang memenuhi
a j .start ≥ a x .end, maka kita bisa mendapatkan subpersoalan activity selection dengan kegiatan
dari j sampai N, seperti yang diilustrasikan pada Gambar 6.1.
6.3 Greedy Choice
Persoalan yang dapat dicari subpersoalannya belum tentu dapat diselesaikan dengan teknik
greedy . Pada setiap subpersoalan, harus terdapat langkah yang bisa dilakukan yang mana dapat
menghasilkan solusi optimal pada subpersoalan tersebut, atau biasa disebut greedy choice .
Pada persoalan activity selection, ada beberapa langkah yang dapat dilakukan, diantaranya
memilih aktivitas dengan waktu mulai paling awal, aktivitas dengan durasi tersingkat, ataupun
aktivitas dengan waktu akhir paling awal. Namun, tidak semua pilihan tersebut merupakan pilihan
yang optimal.
• Memilih aktivitas dengan waktu mulai paling awal.
Gambar 6.2: Kasus yang mana memilih aktivitas dengan waktu mulai paling awal tidak optimal.
Sekilas, pemilihan ini merupakan langkah yang optimal. Namun, bisa jadi ada aktivitas
yang mulai lebih awal, tetapi memiliki durasi yang sangat panjang sehingga menyita waktu,
seperti yang diilustrasikan pada Gambar 6.2. Dengan kata lain, pilihan ini tidak selalu
menghasilkan solusi optimal.
• Memilih aktivitas dengan durasi paling singkat.
Gambar 6.3: Kasus yang mana memilih aktivitas dengan durasi tersingkat tidak optimal.
Serupa dengan pemilihan sebelumnya, ternyata pemilihan ini tidak menjamin solusi yang
57