Efektivitas Algoritma Greedy Pada Coin Change Problem: Studi Komparatif dengan Dynamic Programming
Abstract
Coin Change Problem merupakan salah satu permasalahan optimasi klasik yang bertujuan menentukan jumlah koin atau lembar uang minimum untuk membentuk suatu nilai nominal tertentu. Berbagai metode optimasi telah diusulkan untuk menyelesaikan permasalahan ini, salah satunya Algoritma Greedy yang dikenal sederhana, efisien, dan memiliki kebutuhan komputasi rendah. Penelitian ini menganalisis efektivitas Algoritma Greedy dalam menyelesaikan Coin Change Problem menggunakan bahasa pemrograman Object Pascal dengan struktur data larik (array), serta membandingkannya secara empiris dengan Dynamic Programming baik pada sistem pecahan Rupiah maupun sistem pecahan non-kanonik. Kebaruan penelitian ini terletak pada analisis eksperimental komparatif terhadap kompleksitas praktis, penggunaan memori, serta batas empiris optimalitas algoritma. Penelitian menggunakan metode eksperimen, dengan pengukuran waktu eksekusi melalui repeated-trial benchmarking pada sepuluh nilai nominal Rupiah dan lima belas nilai nominal pada sistem pecahan hipotetis {1, 3, 4}. Hasil pengujian menunjukkan bahwa Algoritma Greedy menghasilkan jumlah pecahan yang identik dengan solusi optimal Dynamic Programming pada seluruh data uji sistem Rupiah, dengan waktu eksekusi hingga sekitar 185.000 kali lebih cepat pada nominal terbesar. Namun, pada sistem pecahan non-kanonik, Algoritma Greedy gagal mencapai solusi optimal pada 20 persen data uji. Temuan ini menegaskan bahwa keunggulan praktis Algoritma Greedy sangat dibatasi oleh sifat kanonik dari sistem pecahan yang digunakan.
Kata Kunci: Algoritma Greedy; Coin Change Problem; Dynamic Programming; Optimasi; Benchmarking Komparatif.
References
(1983). Data structures and algorithms. Addison-Wesley.
Cai, X. (2008). Canonical coin systems for change-making problems. arXiv:0809.0400. from https://arxiv.org/abs/0809.0400
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms (4th ed.). MIT Press.
Gupta, S., Huang, B., & Impagliazzo, R. (2024). The greedy coin change problem. arXiv:2411.18137. from https://arxiv.org/abs/2411.18137
Jensen, K., & Wirth, N. (1991). Pascal user manual and report. Springer.
Kozen, D., & Zaks, S. (1994). Optimal bounds for the change-making problem. Theoretical Computer Science, 123(2), 377–388.
Mehmood, A. (2019). ASH CC Algo: Coin change algorithm optimization. International Journal of Computer Applications, 178(15), 21–25.
Pearson, D. (2005). A polynomial-time algorithm for the change-making problem. Operations Research Letters, 33(3), 231–234.
Sunandar, H., & Pristiwanto. (2019). Optimalisasi implementasi algoritma greedy dalam fungsi penukaran mata uang Rupiah. Jurnal Teknik Informatika UNIKA Santo Thomas, 4(2), 193–201.
