Vícerozměrná úloha batohu

This paper focuses on a frequently used application of combinatorial optimization, the knapsack problem. The goal of the knapsack problem is to decide which items, potentially in what number and location, to place in a bounded space so that the resulting placement yields the highest utility. Due to the nature of this problem, it is an integer problem and therefore finding the result can be difficult, especially when applying the problem to larger dimensions. For one-dimensional, two-dimensional and multi-dimensional problems, the mathematical model is also dependent on the maximum number of objects given, which further differentiates and complicates the problem. There are many ways to classify and subsequently solve this type of problems. In addition, new optimization techniques are constantly being developed. The goal of this paper will be to categorize knaspacking problems in general, describe them including their real-world applications, and formulate their economic and mathematical models. The main objective is to create an application that allows the user to easily define the problem and find the optimal solution to a multidimensional knapsack problem, one of the types of knapsack problems that is extended by an additional dimension compared to the traditional one.