Analisis Kinerja Algoritma Greedy dalam Penyelesaian Masalah Knapsack - Isralestina, Fathiah; Ujianto, Nur Tulus; Khoirunnisa, Khoirunnisa; Fitriyah, Aidah; Fanti, Azizah Permata (Journal of Information System & Business Management (ISBM), 2025)
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.