Call for Paper

CAE solicits original research papers for the July 2023 Edition. Last date of manuscript submission is June 30, 2023.

Read More

Greedy Approach for Optimizing 0-1 Knapsack Problem

SocButtons v1.5

Shafiqul Abidin. Published in Applied Mathematics.

Greedy Approach for Optimizing 0-1 Knapsack Problem
Communications on Applied Electronics
Year of Publication: 2017
Publisher: Foundation of Computer Science (FCS), NY, USA
Series: Volume 7 Number 6
Authors: Shafiqul Abidin
10.5120/cae2017652675
Download full text

Shafiqul Abidin. Greedy Approach for Optimizing 0-1 Knapsack Problem. Communications on Applied Electronics 7(6):1-3, September 2017. BibTeX

@article{10.5120/cae2017652675,
	author = {Shafiqul Abidin},
	title = {Greedy Approach for Optimizing 0-1 Knapsack Problem},
	journal = {Communications on Applied Electronics},
	issue_date = {September 2017},
	volume = {7},
	number = {6},
	month = {Sep},
	year = {2017},
	issn = {2394-4714},
	pages = {1-3},
	numpages = {3},
	url = {http://www.caeaccess.org/archives/volume7/number6/758-2017652675},
	doi = {10.5120/cae2017652675},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

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.

References

  1. Yang Liu The Genetic Algorithm of Solving 0- 1’sKnapsack Problem and Its Improvement[J] Tianjin Normal University Natural Science Edition 9/2003J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68–73.
  2. Wenlan Chen, Jian Hua Liu a genetic algorithm in Solving a knapsack problem Computer of FuJian 5/2006.
  3. TanShan Yan Greedy algorithm based on Hybrid Genetic Algorithm for Solving 0 / 1 knapsack problem Research and Development 7/2006.
  4. HongWei Huo,Jin Xu,Zheng Bao Solv ing 0-1 knapsack problem us ing genetic algorithm The Journal of Xi'an University of Electronic Science and Technology August 1999.
  5. GuangLin Shi, WeiXiang Shi Genetic Algorithm and its New Progress in Research and Application Basic science April of 1997.
  6. Shafiqul Abidin, A Novel Construction of Secure RFID Authentication Protocol”, International Journal of Security, Computer Science Journal, Malaysia, Vol. 8, Issue 8, October 2014.
  7. Shafiqul Abidin, Key Agreement Protocols and Digital Signature Algorithm” International Journal of Current Advanced Research, August, 2017.

Keywords

Genetic Algorithm, 0-1 Knapsack Problem, Greedy Strategy.