My first Magazine pemrograman-kompetitif-dasar | Page 71

6.6 Pembuktian Greedy
Contoh Soal 6.2: Penukaran Uang
Anda ingin menukar uang Rp12.000 dengan lembaran uang kertas Rp5.000, Rp2.000, dan
Rp1.000. Anda ingin menukar dengan jumlah lembaran sesedikit mungkin.
Pada soal tersebut, greedy choice yang terpikirkan adalah dengan memilih lembaran dengan
nominal terbesar yang mungkin untuk tiap subpersoalan. Pertama kita pilih lembaran Rp5.000,
sehingga tersisa Rp7.000 lagi yang harus dipecah. Selanjutnya kita pilih Rp5.000 lagi dan
menyisakan Rp2.000 untuk dipecah. Akhirnya, kita pilih Rp2.000 sebagai pecahan terakhir.
Solusi dari kasus ini adalah dengan menggunakan 3 lembaran.
Dengan soal yang sama, bagaimana jika lembaran rupiah yang beredar bernilai Rp5.000,
Rp4.000, dan Rp1.000? Dengan algoritma greedy , kita akan menukar Rp12.000 dengan
lembaran Rp5.000, Rp5.000, Rp1.000, dan Rp1.000. Padahal ada solusi yang lebih baik, yaitu
menggunakan 3 lembaran Rp4.000. Pada kasus tersebut, greedy choice yang tidak selalu dapat
menghasilkan solusi optimal. Permasalahan ini tidak dapat diselesaikan oleh algoritma greedy .
Permasalahan ini bisa diselesaikan dengan algoritma dynamic programming, yang akan dibahas
pada Bab 7.
6.6
Pembuktian Greedy
Biasanya akan ada beberapa pilihan greedy choice yang ada, yang mana tidak semuanya
bisa menghasilkan solusi optimal. Ketika menemukan suatu greedy choice , sangat dianjurkan
untuk menguji kebenaran dari pilihan tersebut sebelum diimplementasikan. Namun, pembuktian
kebenaran algoritma greedy tidaklah mudah.
Pengujian yang dapat dilakukan adalah dengan mencoba membuat contoh kasus yang dapat
menggagalkan greedy choice tersebut. Teknik ini biasa disebut proof by counterexample. Jika
ditemukan satu saja contoh kasus yang mana greedy choice yang diajukan tidak menghasilkan
solusi optimal, maka greedy choice tersebut dinyatakan salah. Namun, bila Anda tidak bisa
menemukan counterexample, belum tentu algoritma Anda benar.
Algoritma greedy terkadang mudah untuk dipikirkan dan mudah untuk diimplementasikan,
namun sulit untuk dibuktikan kebenarannya. Pembuktian kebenaran algoritma greedy bisa jadi
membutuhkan pembuktian matematis yang kompleks dan memakan waktu. Oleh karena itu, pada
suasana kompetisi, intuisi dan pengalaman sangat membantu untuk menyelesaikan soal bertipe
greedy . Berhati-hati dan teliti saat mengerjakan soal bertipe greedy . Perhatikan setiap detil
yang ada, karena bisa berakibat fatal.
61