My first Magazine pemrograman-kompetitif-dasar

6 Greedy Greedy merupakan sebuah teknik dalam strategi penyelesaian masalah, bukan suatu algo- ritma khusus. Teknik greedy biasanya memiliki waktu eksekusi yang cepat dan biasanya mudah untuk diimplementasikan, namun terkadang sulit dibuktikan kebenarannya. Pada bab ini kita akan mempelajari cara greedy bekerja melalui pembahasan permasalahan greedy klasik: Activity Selection . 6.1 Konsep Greedy Suatu persoalan dapat diselesaikan dengan teknik greedy jika persoalan tersebut memiliki memiliki sifat berikut: • Solusi optimal dari persoalan dapat ditentukan dari solusi optimal subpersoalan tersebut. • Pada setiap subpersoalan, ada suatu langkah yang bisa dilakukan yang mana langkah tersebut menghasilkan solusi optimal pada subpersoalan tersebut. Langkah ini disebut juga greedy choice . Untuk menguasai teknik greedy , diperlukan banyak latihan. Sebagai awalan, kita akan mempelajari salah satu permasalahan greedy klasik yang biasa disebut Activity Selection . Contoh Soal 6.1: Activity Selection Anda diberikan N buah aktivitas. Aktivitas ke-i dinyatakan dalam ha i .start, a i .endi. Artinya, aktivitas ini dimulai pada waktu a i .start dan berakhir pada waktu a i .end. Pada setiap satuan waktu, Anda dapat mengikuti paling banyak satu aktivitas. Dengan kata lain, Anda dapat mengikuti dua aktivitas i dan j jika a i .end ≤ a j .start atau a j .end ≤ a i .start. Anda ingin mengatur jadwal sedemikian sehingga Anda bisa mengikuti aktivitas sebanyak mungkin. Contoh Aktivitas: [h1, 3i, h2, 6i, h5, 7i, h8, 9i] Solusi: Anda dapat hadir di 3 aktivitas berbeda yang tidak saling tumpang tindih, yaitu h1, 3i, h5, 7i, dan h8, 9i 6.2 Menemukan Subpersoalan Langkah awal dalam menyelesaikan permasalahan dengan teknik greedy adalah memastikan bahwa soal dapat dipecah menjadi subpersoalan yang lebih kecil. 56

My first Magazine pemrograman-kompetitif-dasar | Page 66