David Kuhlen and Andreas Speck, Germany

The knapsack problem is a classical optimization problem in computer science that can be efficiently solved using an algorithm based on dynamic programming. This study investigates the impact of technical factors such as the number of elements, the size of the knapsack, or the sorting of elements on the performance of the algorithm. Performance refers to the speed of the algorithm implementation in solving the problem. The analysis focuses on so-called Performance Impact Factors, which are the selected influences that can affect the speed of the algorithm. While the size of the considered knapsack represents a parameterization/configuration, the number of items is directly related to the problem itself; therefore, the term Performance Impact Factors is generally used. The investigation is based on a simulation experiment. The analysis of the simulation experiment data shows that as the total number of elements and the knapsack capacity increase, the algorithm's runtime also increases. In this context, an increase in knapsack capacity has a more pronounced negative effect on the algorithm's runtime. An examination of sorting strategies further reveals that a prior sorting of elements by value in descending order can lead to significant deteriorations in runtime.

Dynamic Programming, Knapsack Problem, Performance