Review on Algorithmic Approaches to Solving Knapsack Problem
Yosra Ali Hassan *
IT Department, Technical College of Informatics Akre, Akre University for Applied Sciences, Iraq.
Ibrahim Mahmood Ibrahim
Department Computer Networks and Information Security, Technical College of Informatics-Akre, Akre University for Applied Sciences, Iraq.
*Author to whom correspondence should be addressed.
Abstract
The knapsack problem is a classic optimization challenge where the objective is to maximize the total value of items packed into a knapsack without exceeding its weight capacity It comes in several variants, including the 0–1 Knapsack Problem (0-1KP), the Multidimensional Knapsack Problem (MDKP), and the Quadratic Knapsack Problem (QKP). This Review paper conducts a detailed exploration and analysis of algorithmic strategies developed for solving the knapsack problem (KP). The paper delves into various algorithmic approaches, including advanced dynamic programming, heuristic and metaheuristic algorithms like genetic algorithms and simulated annealing. The goal is to provide a comprehensive comparison and evaluation of these diverse algorithmic approaches, examining their performance, efficiency, and applicability in various real-world scenarios. By highlighting the strengths, weaknesses, and recent developments in knapsack problem-solving algorithms, this review aims to guide future research and help practitioners make informed choices.
Keywords: Knapsack problem, algorithmic, multidimensional knapsack problem, quadratic knapsack problem