Towards Enhancing Energy Consumption and Time Complexity of Combinatorial Algorithms for Solving the Knapsack Problem

Abstract

The increasing demand for energy-efficient and time-optimized computational systems has driven research into combinatorial algorithms, particularly those used to solve the knapsack problem. The knapsack problem is one of the most significant in combinatorial optimization, which involves determining the optimal selection of items to include in a knapsack while adhering to specific constraints, such as weight or profit limits. This study compares the energy consumption and time complexity of the greedy and dynamic programming algorithms applied to this problem. Using power models to measure total energy consumption and execution time, the research reveals that the greedy algorithm is far more efficient, with negligible energy consumption across various scenarios. In contrast, the dynamic programming algorithm, while delivering accurate solutions, consumes more energy and takes longer due to its memory-intensive operations. These findings highlight the need to consider energy and time efficiency in algorithm design, contributing to more sustainable computing practices. Future research will explore larger datasets and focus on instruction-level energy analysis to optimize algorithm performance.