Proposal of OptDG Algorithm for Solving the Knapsack Problem

In a computational complexity theory, P, NP, NP-complete and NP-hard problems are divided into complexity classes which are used to emphasize how challenging it is to solve particular types of problems. The Knapsack problem is a well-known computational complexity theory and fundamental NP-hard optimization problem that has applications in a variety of disciplines. Being one of the most well-known NP-hard problems, it has been studied extensively in science and practice from theoretical and practical perspectives. One of the solution to the Knapsack problem is the Dantzig’s greedy algorithm which can be expressed as a linear programming algorithm which seeks to discover the optimal solution to the knapsack problem. In this paper, an optimized Dantzig greedy (OptDG) algorithm that addresses frequent edge cases, is suggested. Furthermore, OptDG algorithm is compared with the Dantzig’s greedy and optimal dynamically programmed algorithms for solving the Knapsack problem and performance evaluation is conducted.

@article{Arlovic2024,
  title     = {Proposal of OptDG Algorithm for Solving the Knapsack Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {15},
  number    = {9},
  year      = {2024},
  publisher = {The Science and Information Organization},
  author    = {Matej Arlovic and Tomislav Rudec and Josip Miletic and Josip Balen},
  doi       = {10.14569/IJACSA.2024.0150998},
  url       = {https://doi.org/10.14569/IJACSA.2024.0150998}
}