Home / Vol. 3 - No. 1 / Article
ANALISIS KINERJA ALGORITMA GREEDY DALAM PENYELESAIAN MASALAH KNAPSACK
Abstract
Penelitian ini bertujuan untuk menganalisis kinerja algoritma Greedy dalam penyelesaian Knapsack Problem (KP), khususnya dalam menghasilkan solusi mendekati optimal dan mengevaluasi efisiensi waktu eksekusi pada berbagai skenario ukuran data dan kapasitas. Data penelitian berupa himpunan item dengan bobot dan nilai yang dihasilkan secara acak, mencakup jumlah item sebanyak 10, 50, 100, 500, dan 1000, serta kapasitas knapsack berkisar antara 30% hingga 70% dari total bobot item. Hasil eksperimen menunjukkan bahwa algoritma Greedy memberikan solusi dengan akurasi 80% hingga 98%, di mana akurasi tertinggi dicapai pada dataset kecil dan menurun signifikan seiring bertambahnya ukuran item. Dari segi efisiensi waktu, algoritma Greedy terbukti unggul dengan peningkatan waktu eksekusi yang bersifat linier, sementara metode pembanding, Dynamic Programming (DP), membutuhkan waktu eksponensial yang jauh lebih besar, terutama pada dataset besar. Kesimpulan penelitian ini menunjukkan bahwa algoritma Greedy efektif untuk permasalahan berskala besar yang membutuhkan efisiensi waktu, namun memiliki keterbatasan dalam mencapai solusi optimal. Penelitian lanjutan disarankan untuk mengombinasikan algoritma Greedy dengan metode metaheuristik atau pendekatan machine learning guna meningkatkan akurasi tanpa mengorbankan efisiensi waktu komputasi.
Referensi
Abdel-Basset, M., Mohamed, R., Elkomy, O. M., & Abouhawwash, M. (2022). Recent metaheuristic algorithms with genetic operators for high-dimensional knapsack instances: A comparative study. Computers & Industrial Engineering, 166, 107974. https://doi.org/10.1016/j.cie.2022.107974
Boes, D. F., Dewanto, K. P., Raushanfikir, M. I., Handoyo, A. T., & Nurhasanah. (2023). Analyzing The Most Effective Algorithm For Knapsack Problems. 2023 3rd International Conference on Smart Cities, Automation & Intelligent Computing Systems (ICON-SONICS), 171–176. https://doi.org/10.1109/ICON- SONICS59898.2023.10434966
Cacchiani, V., Iori, M., Locatelli, A., & Martello, S. (2022). Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research, 143, 105693. https://doi.org/10.1016/j.cor.2021.105693
Chen, X. (2022). A Comparison of Greedy Algorithm and Dynamic Programming Algorithm. SHS Web of Conferences. https://doi.org/10.1051/shsconf/202214403009
D’Ambrosio, C., Laureana, F., Raiconi, A., & Vitale, G. (2023). The Knapsack Problem with forfeit sets. Computers & Operations Research, 151, 106093. https://doi.org/10.1016/j.cor.2022.106093
Dande, B., Chen, P.-Y., & Wei, H.-Y. (2024). An Integrated Charging and Computation Scheduling of Electric Vehicles in Edge Computing System. IEEE Transactions on Intelligent Transportation Systems, 1–19. https://doi.org/10.1109/TITS.2024.3495973
Kazakovtsev, L. A., & Rozhnov, I. (2020). Application of algorithms with variable greedy heuristics for k-medoids problems. Informatica, 44(1). https://doi.org/10.31449/inf.v44i1.2737
Li, W., Xia, L., Huang, Y., & Mahmoodi, S. (2022). An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems. Journal of Ambient Intelligence and Humanized Computing, 13(3), 1557–1571. https://doi.org/10.1007/s12652-021-03120-0
Luo, Z., Guo, X., Wen, B., & Cao, J. (2022). An Evolution Algorithm Based on Cloud Model for 0-1 Knapsack Problem. 2022 15th International Symposium on Computational Intelligence and Design (ISCID), 147–150. https://doi.org/10.1109/ISCID56505.2022.00040
Mishra, S., & Perkins, D. (2023). Using Heuristic Algorithms to Solve the 0-1 Knapsack Problem. Journal of Student Research. https://doi.org/10.47611/jsrhs.v12i4.5660
Missaoui, A., Ozturk, C., & O’Sullivan, B. (2023). Iterated Greedy Algorithms for Combinatorial Optimization: A Systematic Literature Review. 2023 20th ACS/IEEE International Conference on Computer Systems and Applications (AICCSA), 1–7. https://doi.org/10.1109/AICCSA59173.2023.10479246
Moradi, N., Kayvanfar, V., & Rafiee, M. (2021). An efficient population-based simulated annealing algorithm for 0–1 knapsack problem. Engineering with Computers, 38, 2771–2790. https://doi.org/10.1007/s00366-020-01240-3
Pronzato, L. (2022). Performance analysis of greedy algorithms for minimising a Maximum Mean Discrepancy. Statistics and Computing, 33(1), 14. https://doi.org/10.1007/s11222-022-10184-1
Qin, H.-X., Han, Y.-Y., Zhang, B., Meng, L.-L., Liu, Y.-P., Pan, Q.-K., & Gong, D.-W. (2022). An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem. Swarm and Evolutionary Computation, 69, 100992. https://doi.org/10.1016/j.swevo.2021.100992