Analisis Kinerja Algoritma Greedy dalam Penyelesaian Masalah Knapsack
Article Sidebar
Published:
Mar 25, 2025
Keywords:
Efisiensi Waktu, Knapsack Problem, Optimalisasi, Solusi Greedy, Ukuran Data
Main Article Content
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.
Article Details
Issue
Section
Articles
References
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
Schoot Uiterkamp, M. H. H., Gerards, M. E. T., & Hurink, J. L. (2022). On a reduction for a class of resource allocation problems. INFORMS Journal on Computing, 34(3), 1387–1402. https://doi.org/10.1287/ijoc.2021.1104
Shewale, A., Mokhade, A., Funde, N., & Bokde, N. D. (2020). An Overview of Demand Response in Smart Grid and Optimization Techniques for Efficient Residential Appliance Scheduling Problem. In Energies (Vol. 13, Issue 16). https://doi.org/10.3390/en13164266
Tang, J., Tang, X., Lim, A., Han, K., Li, C., & Yuan, J. (2020). Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5, 1–22. https://doi.org/10.1145/3447386
Truong, T. K. (2021). A New Moth-Flame Optimization Algorithm for Discounted {0-1} Knapsack Problem. Mathematical Problems in Engineering. https://doi.org/10.1155/2021/5092480
Usman, B. Bin, Kanoma, S. I., Zakariyau, I., Niworu, H. A., & Rilwan, A. A. (2024). Exploring Heuristic Algorithms for the Knapsack Problem: A Comparative Analysis of Program Complexity and Computational Efficiency. Kasu Journal of Computer Science. https://doi.org/10.47514/kjcs/2024.1.2.0017
Van Dam, W., Eldefrawy, K., Genise, N., & Parham, N. (2021). Quantum optimization heuristics with an application to knapsack problems. 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 160–170. https://doi.org/10.1109/QCE52317.2021.00033
Violina, S. (2020). Analysis of Greedy and Backtracking Algorithm on Knapsack Problem. Solid State Technology, 63, 3787–3791. https://consensus.app/papers/analysis-of-greedy-and-backtracking-algorithm-on-knapsack-violina/0298f6085ebb5622a6d4b291f56b8264/
Wu, Y. (2023). Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem. Applied and Computational Engineering. https://doi.org/10.54254/2755-2721/5/20230666
Yang, H., & Guo, X. (2020). An Efficient Heuristic Algorithm for Solving 0-1 Knapsack Problem. Journal of Physics: Conference Series, 1865. https://doi.org/10.1088/1742-6596/1865/4/042009
Zhang, J., Jiang, W., & Zhao, K. (2024). An Improved Shuffled Frog-Leaping Algorithm to Solving 0–1 Knapsack Problem. IEEE Access, 12, 148155–148166. https://doi.org/10.1109/ACCESS.2024.3424415
Zhao, J., & Hifi, M. (2024). A Cooperative Method for Solving the Set-Union Knapsack Problem. 2024 10th International Conference on Control, Decision and Information Technologies (CoDIT), 1219–1224. https://doi.org/10.1109/CoDIT62066.2024.10708580
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
Schoot Uiterkamp, M. H. H., Gerards, M. E. T., & Hurink, J. L. (2022). On a reduction for a class of resource allocation problems. INFORMS Journal on Computing, 34(3), 1387–1402. https://doi.org/10.1287/ijoc.2021.1104
Shewale, A., Mokhade, A., Funde, N., & Bokde, N. D. (2020). An Overview of Demand Response in Smart Grid and Optimization Techniques for Efficient Residential Appliance Scheduling Problem. In Energies (Vol. 13, Issue 16). https://doi.org/10.3390/en13164266
Tang, J., Tang, X., Lim, A., Han, K., Li, C., & Yuan, J. (2020). Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5, 1–22. https://doi.org/10.1145/3447386
Truong, T. K. (2021). A New Moth-Flame Optimization Algorithm for Discounted {0-1} Knapsack Problem. Mathematical Problems in Engineering. https://doi.org/10.1155/2021/5092480
Usman, B. Bin, Kanoma, S. I., Zakariyau, I., Niworu, H. A., & Rilwan, A. A. (2024). Exploring Heuristic Algorithms for the Knapsack Problem: A Comparative Analysis of Program Complexity and Computational Efficiency. Kasu Journal of Computer Science. https://doi.org/10.47514/kjcs/2024.1.2.0017
Van Dam, W., Eldefrawy, K., Genise, N., & Parham, N. (2021). Quantum optimization heuristics with an application to knapsack problems. 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 160–170. https://doi.org/10.1109/QCE52317.2021.00033
Violina, S. (2020). Analysis of Greedy and Backtracking Algorithm on Knapsack Problem. Solid State Technology, 63, 3787–3791. https://consensus.app/papers/analysis-of-greedy-and-backtracking-algorithm-on-knapsack-violina/0298f6085ebb5622a6d4b291f56b8264/
Wu, Y. (2023). Comparison of dynamic programming and greedy algorithms and the way to solve 0-1 knapsack problem. Applied and Computational Engineering. https://doi.org/10.54254/2755-2721/5/20230666
Yang, H., & Guo, X. (2020). An Efficient Heuristic Algorithm for Solving 0-1 Knapsack Problem. Journal of Physics: Conference Series, 1865. https://doi.org/10.1088/1742-6596/1865/4/042009
Zhang, J., Jiang, W., & Zhao, K. (2024). An Improved Shuffled Frog-Leaping Algorithm to Solving 0–1 Knapsack Problem. IEEE Access, 12, 148155–148166. https://doi.org/10.1109/ACCESS.2024.3424415
Zhao, J., & Hifi, M. (2024). A Cooperative Method for Solving the Set-Union Knapsack Problem. 2024 10th International Conference on Control, Decision and Information Technologies (CoDIT), 1219–1224. https://doi.org/10.1109/CoDIT62066.2024.10708580