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

Yogesh Awasthi - Lebanese French University, Erbil-KR, Iraq
Ashish Sharma - Lebanese French University, Erbil-KR, Iraq

Citation Format:



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— Running Time; Complexity; B&B; Genetic; Greedy; DP.

Full Text:



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. Bulï¬n. 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).