Bashar Bin Usman^1,, Ibrahim Abdullahi¹, Okeyinka Aderemi Elisha¹

The Knapsack problem is a combinatorial optimization problem for which finding an exact solution using exhaustive search methods is impractical. Therefore, approximate algorithms are usually considered when tackling this optimization problem. The goal of this study was to analyze the complexity of the Knapsack problem using three approximate algorithms: greedy, dynamic programming, and branch-and-bound methods. To achieve this, we measured the Halstead metrics and computational time complexity of these three algorithms. Our methodology involved solving a hypothetical Knapsack problem using the three algorithms in the same programming environment. Experiments were conducted with varying input datasets, and the time complexities of the algorithms were recorded for each experiment. The average time complexities were computed at the end of the experiments. Additionally, we calculated the Halstead metrics required for the study. Both the Halstead metrics and computational time metrics for the three algorithms were then compared. Our findings showed that the greedy approach was the most efficient heuristic, followed closely by the dynamic programming method, with the branch-and-bound algorithm being the least efficient. Future work will incorporate real-world data with specific item characteristics to enhance the relevance and applicability of the findings. Additionally, it will explore hybrid approaches that combine these algorithms to leverage their respective strengths and effectively address their weaknesses.

heuristics, complexity, knapsack problem, greedy, branch-and-bound, dynamic programming, halstead metrics