Abstract

Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc¡¦.
In this paper we will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them.
Greedy and Genetic algorithms can be used to solve the 01 Knapsack problem within a reasonable time complexity. The worstcase time complexity (BigO) of both algorithms is O(N). Nevertheless, these algorithms cannot find the exact solution to the problem. they are helpful in finding a local optimal result only. Our main contribution here is to test both algorithms against wellknown benchmark data sets and to measure the accuracy of the results provided by each algorithm. In other words, we will compare the best local result produced by the algorithm against the real exact optimal result.
