CFP last date
01 May 2024
Call for Paper
June Edition
CAE solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 01 May 2024

Submit your paper
Know more
The week's pick
Responsive image
An Improve Shannon Fano Data Compression Algorithm using Residue Number System

T.D. Lawal L.O. Olatunbosun K.A. Gbolagade
Random Articles
Reseach Article

Greedy Approach for Optimizing 0-1 Knapsack Problem

by Shafiqul Abidin
journal cover thumbnail

Communications on Applied Electronics
Foundation of Computer Science (FCS), NY, USA
Volume 7 - Number 6
Year of Publication: 2017
Authors: Shafiqul Abidin
10.5120/cae2017652675

Shafiqul Abidin . Greedy Approach for Optimizing 0-1 Knapsack Problem. Communications on Applied Electronics. 7, 6 ( Sep 2017), 1-3. DOI=10.5120/cae2017652675

@article{ 10.5120/cae2017652675,
author = { Shafiqul Abidin },
title = { Greedy Approach for Optimizing 0-1 Knapsack Problem },
journal = { Communications on Applied Electronics },
issue_date = { Sep 2017 },
volume = { 7 },
number = { 6 },
month = { Sep },
year = { 2017 },
issn = { 2394-4714 },
pages = { 1-3 },
numpages = {9},
url = { https://www.caeaccess.org/archives/volume7/number6/758-2017652675/ },
doi = { 10.5120/cae2017652675 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-09-04T20:03:14.798652+05:30
%A Shafiqul Abidin
%T Greedy Approach for Optimizing 0-1 Knapsack Problem
%J Communications on Applied Electronics
%@ 2394-4714
%V 7
%N 6
%P 1-3
%D 2017
%I Foundation of Computer Science (FCS), NY, 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.
Index Terms

Computer Science
Information Sciences

Keywords

Genetic Algorithm 0-1 Knapsack Problem Greedy Strategy.

Powered by PhDFocusTM