To search, Click below search items.


All Published Papers Search Service


Exploring Efficient Solutions for the 0/1 Knapsack Problem


Dalal M. Althawadi, Sara Aldossary, Aryam Alnemari, Malak Alghamdi, Fatema Alqahtani, Atta-ur Rahman, Aghiad Bakry, and Sghaier Chabani


Vol. 24  No. 2  pp. 15-24


One of the most significant issues in combinatorial optimization is the classical NP-complete conundrum known as the 0/1 Knapsack Problem. This study delves deeply into the investigation of practical solutions, emphasizing two classic algorithmic paradigms, brute force, and dynamic programming, along with the metaheuristic and nature-inspired family algorithm known as the Genetic Algorithm (GA). The research begins with a thorough analysis of the dynamic programming technique, utilizing its ability to handle overlapping subproblems and an ideal substructure. We evaluate the benefits of dynamic programming in the context of the 0/1 Knapsack Problem by carefully dissecting its nuances in contrast to GA. Simultaneously, the study examines the brute force algorithm, a simple yet comprehensive method compared to Branch & Bound. This strategy entails investigating every potential combination, offering a starting point for comparison with more advanced techniques. The paper explores the computational complexity of the brute force approach, highlighting its limitations and usefulness in resolving the 0/1 Knapsack Problem in contrast to the set above of algorithms.


Dynamic programming, Genetic Algorithms, Brute force, Branch and Bound algorithm, knapsack problem, efficiency