Comparative analysis of the efficiency of various dynamic programming algorithms for the knapsack problem

摘要

When designing electronic circuits, we often need to solve discrete optimization problems. One of the basic methods for solving such problems is the method of dynamic programming. The paper is devoted to a comparative study of different versions of the dynamic programming method for the knapsack problem. The formulation of the problem and various versions of dynamic programming method are discussed. These versions are experimentally evaluated on randomly generated instances. We draw conclusions about the efficiency of various variants for dynamic programming based on experimental data.