My first Magazine pemrograman-kompetitif-dasar | Page 68

6 Greedy
optimal. Seperti yang terlihat pada Gambar 6.3, pemilihan ini dapat memotong dua aktivitas
lain yang sebenarnya dapat kita ikuti.
• Memilih aktivitas dengan waktu akhir paling awal.
Gambar 6.4: Contoh pemilihan aktivitas dengan waktu akhir paling awal.
Dengan memilih aktivitas yang selesai lebih awal, kita mempunyai sisa waktu lebih banyak
untuk aktivitas lainnya. Tanpa peduli kapan aktivitas ini mulai atau berapa durasinya,
memilih yang selesai lebih awal pasti menguntungkan. Pilihan ini adalah merupakan
greedy choice , yang selalu menghasilkan solusi optimal.
6.4
Penyelesaian dengan Teknik Greedy
Secara umum, persoalan dapat diselesaikan dengan teknik greedy dengan melakukan greedy
choice untuk mendapatkan subpersoalan, kemudian secara rekursif menyelesaikan subpersoalan
tersebut. Pada kasus activity selection, kita dapat menentukan aktivitas yang akan diikuti pertama
kali. Selanjutnya kita mendapatkan subpersoalan, yang ternyata dapat diselesaikan dengan cara
serupa!
Gambar 6.5: Konfigurasi masukan awal.
Berikut simulasi penyelesaian activity selection menggunakan greedy . Misalkan, Anda
diberikan interval-interval aktivitas h1, 7i, h2, 6i, h5, 7i, h6, 9i, h9, 12i, h10, 12i, h11, 15i, h13, 14i
yang divisualisasikan di Gambar 6.5. Kita akan melakukan serangkaian greedy choice yang
disimulasikan pada Gambar 6.6 sampai Gambar 6.13.
Gambar 6.6: Langkah 1: Pilihan yang ada: h1, 7i, h2, 6i, h5, 7i, h6, 9i, h9, 12i, h10, 12i, h11, 15i,
h13, 14i. Kita pilih interval h2, 6i karena interval tersebut memiliki waktu selesai
paling awal.
58