Title: A review of 0-1 knapsack problem by nature-inspired optimisation algorithms

Authors: Ruchi Chauhan; Nirmala Sharma; Harish Sharma

Addresses: Department of Computer Science and Engineering, Rajasthan Technical University, Kota – 324010, Rajasthan, India ' Department of Computer Science and Engineering, Rajasthan Technical University, Kota – 324010, Rajasthan, India ' Department of Computer Science and Engineering, Rajasthan Technical University, Kota – 324010, Rajasthan, India

Abstract: Nature is the origin of all knowledge. Researches have built nature-inspired optimisation (NIO) algorithms, that follow natural principles to find solutions, for the real life problems. In the binary knapsack problem (0/1KP), a bag (or a knapsack) has to be filled with articles, where each article has a weight and a profit value, the articles are filled in the knapsack, in whole numbers, up to a weight limit, to attain the optimum profit. The 0/1KP does the optimum sub-structure selection from a given set of articles, i.e., there can be different optimum solutions for a given 0/1KP. The aim of this research is to discuss the NIO algorithms innovated for solving the 0/1KP. The review creates foundation, for future research on optimising the 0/1KP, from meta-heuristic NIO techniques.

Keywords: nature-inspired optimisation; NIO; 0-1 knapsack problem; 0/1KP; NP-hard problems; swarm intelligence.

DOI: 10.1504/IJMMNO.2024.143229

International Journal of Mathematical Modelling and Numerical Optimisation, 2024 Vol.14 No.1/2, pp.84 - 107

Received: 16 Sep 2021
Accepted: 08 Aug 2022
Published online: 11 Dec 2024 *