Review on Algorithmic Approaches to Solving Knapsack Problem

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.