Optimizing energy efficiency and computational complexity of combinatorial approaches for solving the knapsack problem

Abstract The increasing complexity of combinatorial algorithms, especially for solving NP-hard problems like the knapsack problem, has heightened the need for energy- and time-efficient computational solutions. This research optimized two heuristics, namely the greedy algorithm (GA) and dynamic programming algorithm (DPA), with the primary goal of investigating their energy consumption and time complexity. By applying power models and instruction-level parallelism (ILP) techniques to measure and optimize their performance across varying problem sizes, a comprehensive comparison was made. The results demonstrate that the optimized algorithms, particularly GA, exhibit significant improvements in both time and energy efficiency, making them more suitable for large-scale, energy-sensitive applications. In contrast, classical DPA, while providing optimal solutions, shows higher time complexity and energy consumption, especially for larger datasets. However, the optimized DPA addresses these inefficiencies, showing marked improvements in both time and energy use across all instances. This study highlights the critical role of algorithmic optimization in achieving a balance between computational performance and sustainability. The findings contribute to the development of energy-efficient algorithms and underscore the importance of considering both time and energy metrics when solving combinatorial problems.