Methods for improving the efficiency of Brute-force algorithm by the example of solving an Unbounded Knapsack Problem

Aye Min Thike, S. Lupin, Min Thu Khaing


A universal method for the exact solution of discrete optimization problems, invariant to search conditions, is the exhaustive search algorithm (Brute Force Algorithm, BFA). Its wide use in practice is limited by the high computational complexity determined by the dimension of the search space. This determines the interest of researchers in finding approaches to limiting the number of considered solutions without losing its accuracy. The issue of increasing the efficiency of the brute force algorithm for solving discrete optimization problems is considered. On the example of the unbounded knapsack problem (Unbounded Knapsack Problem, UKP), we show the possibility of implementing a generator that ensures the exclusion of variants that do not satisfy the conditions of the problem, without calculating the criterion function. The feasibility of generators for multi-threaded BFA applications has also been evaluated. The effectiveness of the proposed approach is confirmed for both sequential and parallel implementations. The results of computational experiments coincide with theoretical calculations. A 4-thread application with an optimized generator provides more than 30-fold acceleration of calculations. The approach under study can be applied to other discrete optimization problems as well.

Full Text:

PDF (Russian)


Wireless Network Topology Optimisation”, International Journal of Electrical, Electronics and Data Communication, vol.7, Iss.4, pp. 14-20, April 2019.

Simon Bonello, [Online]. Available:

Priya Pedamkar, “Brute force algorithm for closest pair problem”, [Online]. Available:

Abhijit Tripathy, “Brute force approach for Travelling Salesman Problem”, [Online]. Available:

Ms. Jahanvi Kolte, Prof. Dhaval Jha, Dr. Rajan Datt, “Strategies for Implementing the Knapsack Problem”, International Journal of Science Technology and Management, Vol. No.6, Issue No. 06, June 2017, pp. 419-427.

Mikhail Posypkin, Si Thu Thant Sin, “Comparative Analysis of the Efficiency of Various Dynamic Programming Algorithms for The Knapsack Problem”, 2016 IEEE NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW), pp. 313-316, 2-3 February 2016, St. Petersburg, Russia.

O.A Balogun, M.A Dosunmu, I.O Ibidapo, “An Explanatory Comparison of Brute Force and Dynamic Programming Techniques to Solve the 0-1 Knapsack Problem”, International Journal of Innovative Science and Research Technology, Vol.7, Issue 2, February 2022, pp. 660-664.

Branch and Bound Algorithm, [Online]. Available:

Mohammad Andri Budiman, Dian Rachmawati, “Using random search and brute force algorithm in factoring the RSA modulus”, Journal of Computing and Applied Informatics (JoCAI), Vol.2, No.1, pp. 45-52, 2018.

Vincent Poirriez, Nicola Yanev, Rumen Andonov, “A Hybrid Algorithm for the Unbounded Knapsack Problem”, Discrete Optimization, Volume 6, 2009, pp. 110-124.

OpenMP. [Online]. Available: OpenMP


  • There are currently no refbacks.

Abava  Absolutech Convergent 2022

ISSN: 2307-8162