On Some Generalizations of the Knapsack Problem

The knapsack problem is one of the most famous discrete optimization problems - its formulation is very simple, although the problem itself is NP-complete. The combination of these two features, as well as a wide range of possible applications in logistics, Economics, and other fields, leads to a high level of research interest in this task. However, this problem has many different variations and formulations, most of which are well understood. In this paper, we will consider another way to generalize the backpack problem, dictated by the desire to link it to the theory of computational complexity. In particular, we consider generalizations for which it is not trivial to define a specific complexity class of the problem, and we also aim to develop approximate algorithms for these generalizations that have an acceptable working time. To achieve these goals, we use standard approaches for such situations: constructing relaxations of initial problems, searching for optimal ones for them, and proving that the optimums of direct problems and their corresponding relaxations differ by no more than a time constant. Chapter 2 is devoted to General formulations of complex-theoretic problems, special cases of which are the classic backpack problem and some of its generalizations, which will be studied in subsequent chapters. We also prove some statements that clarify lower estimates of the complexity of the problem. Chapter 3 deals specifically with the problem of the enemy's knapsack, which is a non-standard but natural generalization of the problem in the classical formulation. For this problem, we present an algorithm that guarantees a constant approximation to find the optimum. Similarly, Chapter 4 deals with the double backpack problem, which is higher than the previously mentioned backpack problems in the complexity hierarchy. For this problem, we also present an algorithm that guarantees constant approximation to the desired value. The obtained approximate algorithms, in turn, are the main result of this work. In this work, the goals set in the introduction were successfully achieved. For the problems of the opposing knapsack and the double knapsack, algorithms were presented that are polynomial in the length of the input signal specified in the unary record, guaranteeing a constant approximation to the estimation of the desired values. The author also considers it important to note that this study leaves a large gap for further study in the future. Questions remain about the complexity of the game problem in binary notation, as well as about a deeper understanding of the structure of a multi-GAME game in General and in individual cases.