ENHANCING COMPUTATIONAL EFFICIENCY IN SOLVING KNAPSACK PROBLEM: INSIGHTS FROM ALGORITHMIC PARALLELIZATION AND OPTIMIZATION

The Knapsack problem is a well-known combinatorial optimization problem where finding an exact solution via exhaustive search is impractical due to its computational complexity. Therefore, approximate algorithms are typically employed to tackle this challenge. This study focuses on optimizing three such algorithms: greedy, dynamic programming, and branch-and-bound. The researchers’ primary objectives include evaluating their time and program complexity, comparing their efficiencies, and enhancing their performance. They utilized advanced parallelization techniques to accelerate the implementation of loop-based optimization algorithms, distributing tasks across multiple processing units concurrently. This approach minimized computational time, improved overall efficiency, and enhanced scalability, thus enabling effective solutions for large-scale optimization problems. Coefficients for the Knapsack model were generated using a random number generation algorithm to ensure a diverse set of test cases. Through detailed analysis and experimental runs, employing Halstead metrics and time complexity measures, the researchers observed significant improvements in the optimized algorithms over classical methods. The enhanced algorithms demonstrated reduced program complexity and superior computational speed, particularly in terms of time complexity across varying input sizes. These findings suggest that the optimized algorithms offer more efficient solutions for the Knapsack problem. This research contributes to advancing theoretical computer science by presenting a novel computational approach to solving complex knapsack-model-based problems. The results have practical implications, offering new tools for addressing real-world challenges across various application areas.