|Communications on Applied Electronics|
|Foundation of Computer Science (FCS), NY, USA|
|Volume 7 - Number 6|
|Year of Publication: 2017|
|Authors: Shafiqul Abidin|
Shafiqul Abidin . Greedy Approach for Optimizing 0-1 Knapsack Problem. Communications on Applied Electronics. 7, 6 ( Sep 2017), 1-3. DOI=10.5120/cae2017652675
Abstract: 0--1 knapsack problem is a typical NP complete problem in field of computer. Traditional knapsack problem is solved recursively using backtracking, branch and bound, dynamic programming and greedy methods. The advantages of using recursive backtracking to solve knapsack problem algorithm are – its simplicity, completely traverse the search space and sure to find the optimal solution. But the solution space is exponential growth, when extended to certain extent. This algorithm will solve the knapsack problem unrealistically. The greedy algorithm can only be used to get Approximate Solution in a certain range near the optimal solution. This paper is based on 0-1 knapsack problem, a mathematical model, and analysis of the greedy strategy. Effort is made to give a genetic algorithm that solves the knapsack problem. Greedy strategy along with the traditional genetic algorithm has been improved that shorten the time of solution. Further, it improves the accuracy of the solution.