期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2016
卷号：16
期号：7
页码：1-10
出版社：International Journal of Computer Science and Network Security
摘要：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.
