To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Comparing between different approaches to solve the 0/1 Knapsack problem |
|
Author |
Ameen Shaheen, Azzam Sleit |
| Citation |
Vol. 16 No. 7 pp. 1-10 |
|
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 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) 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 well-known 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. |
|
Keywords |
0/1 Knapsack, Algorithm, Greedy algorithm, dynamic programming. |
|
URL |
