Contrasting of Various Algorithmic Techniques to Solve Knapsack 0-1 Problem

Yogesh Awasthi - Department of Information Technology, Lebanese French University, College of Engineering and Computer Science, Erbil-KR, Iraq
Ashish Sharma - Department of Information Technology, Lebanese French University, College of Engineering and Computer Science, Erbil-KR, Iraq

Abstract


This paper will point of convergence on a relative assessment and estimation of the dynamic programming, B&B, Greedy and Genetic algorithm including of the intricacy of time prerequisites, and the necessary programming endeavors and inspect the absolute incentive for every one of them. Out of these four, Two algorithm (Greedy and Genetic) algorithm can be utilized to clear up the 0-1 Knapsack issue inside a sensible time multifaceted nature. The most pessimistic scenario time unpredictability (Big-O) of the two calculations is O(N). Parallely, these calculations can't find the accurate response to the issue; they are valuable in detecting a close by premier final product as it were. Our basic commitment directly here is to investigate the two calculations contrary to common benchmark realities units and to quantify the precision of the impacts provided by method for each calculation. In this way, we will think about the top notch neighbourhood result created by utilizing the calculation against the genuine real most dependable outcome.

Keywords


Keywords— Running Time; Complexity; B&B; Genetic; Greedy; DP.

Full Text:

PDF

References


Gossett, Eric. Discreet Mathematics with Proof. New Jersey: Pearson Education Inc., 2013.

Hristakeva, Maya and Dipti Shrestha. “Solving the 0/1 Knapsack Problem with Genetic Algorithms.” MICS 2014 Proceedings. .

S. Mohanty, R. Satapathy, “An evolutionary multiobjective genetic algorithm to solve 0/1 Knapsack Problem,” IEEE Transl.

Beijing, vol. 2, pp. 397–399, August 2009.P.KOLESAR, “A branch and bound algorithm for the knapsack problem. Manage,” Sci, pp. 723-735, May 2018.

Adams, E. Balas, D. Zawack. The Shifting Bottleneck Procedure for Job-Shop Scheduling. Management Science, 34, 3, 391–401, .2017.

Y. Yang, R.L. Bulfin. An exact algorithm for the Knapsack Problem with Setup. Int. J. Operational Research, 5, 280–291, 2018.

George B. Dantzig, Discrete-Variable Extremum Problems, Operations Research Vol. 5, No. 2, April 1957, pp. 266–288,doi:10.1287/opre.5.2.266.

Different Approaches to Solve the 0/1 Knapsack Problem. Maya Hristakeva, Dipti Shrestha; Simpson College.

Rahman K. and Ahmed S. Performance Analysis of Genetic Algorithm for Solving the Multiple-Choice Multi-Dimensional Knapsack Problem. International Journal of Recent Trends in Engineering, 2009, vol. 2, no. 2.2017.

Chen Lin, “A Heuristic Genetic Algorithm Based on Schema Replacement for 0-1 knapsack Problem”, Fourth International Conference on Genetic and Evolutionary Computing 2015

Harish G , A hybrid PSO – GA algorithm for constrained optimization problems Applied Mathematics and Computation (Atlanta, USA: Elsevier) 274 292 – 305,2016.

Cormen T H 2009 Introduction to algorithms (third edition) (MIT press).




DOI: http://dx.doi.org/10.30630/joiv.4.1.333

Citation Format:

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

__________________________________________________________________________
JOIV : International Journal on Informatics Visualization
ISSN 2549-9610  (print) | 2549-9904 (online)
Organized by Department of Information Technology - Politeknik Negeri Padang, and Institute of Visual Informatics - UKM and Soft Computing and Data Mining Centre - UTHM
Published by Department of Information Technology - Politeknik Negeri Padang
W : http://joiv.org
E : joiv@pnp.ac.id, rahmat@pnp.ac.id

View JOIV Stats

 

 


Creative Commons License is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.