ANALISIS PERBANDINGAN KINERJA ALGORITMA PEMROGRAMAN DINAMIS DAN GREEDY DALAM PENYELESAIAN MASALAH KNAPSACK

Abstrak

The Knapsack problem is a classic optimization challenge with wide-ranging applications across various fields. This research compares the performance of Dynamic Programming (DP) and Greedy algorithms in solving the Knapsack problem, focusing on the trade-off between solution optimality and computational efficiency. Through a series of experiments using diverse datasets, we evaluate execution time, solution quality, memory usage, and scalability of both algorithms. Results indicate that DP consistently produces optimal solutions but faces scalability challenges for large instances, while Greedy excels in speed and memory efficiency but yields sub-optimal solutions. Analysis on real-world datasets reveals DP's superiority in long-term logistics optimization and Greedy's suitability for real-time e-commerce applications. This study provides guidance for algorithm selection based on problem characteristics and application requirements, and identifies future research directions including hybrid and adaptive approaches.