To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Exploring Efficient Solutions for the 0/1 Knapsack Problem |
|
Author |
Dalal M. Althawadi, Sara Aldossary, Aryam Alnemari, Malak Alghamdi, Fatema Alqahtani, Atta-ur Rahman, Aghiad Bakry, and Sghaier Chabani |
| Citation |
Vol. 24 No. 2 pp. 15-24 |
|
Abstract |
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. |
|
Keywords |
Dynamic programming, Genetic Algorithms, Brute force, Branch and Bound algorithm, knapsack problem, efficiency |
|
URL |
