Evaluating Heuristic Approaches for Solving the 0/1 Knapsack and MMKP: A Comparative Study

This study presents a comprehensive analysis of three heuristic algorithms, Simulated Annealing (SA), Genetic Algorithm (GA), and a hybrid approach combining SA and GA to solve the 0/1 Knapsack Problem (0/1KP) and its variant, the Multidimensional Multiple-Choice Knapsack Problem (MMKP). To evaluate the performance, two custom datasets were created: one for the 0/1 Knapsack Problem and another for the MMKP with multiple constraints. Results revealed GA outperforms SA and the hybrid approach in solving the 0/1KP, showing the fastest runtime, lower statistical indicators, and lower time complexity. For the MMKP, SA demonstrates superior performance over GA and the hybrid model, making it the preferred choice for complex scenarios. These findings highlight the importance of choosing algorithms based on problem complexity and application constraints, offering insights into real-world scenarios. This study enhances the understanding of heuristic optimization methods in combinatorial problems, offering practical insights into selecting the most efficient algorithm based on problem characteristics and real-world scenarios.