Method for solving the Backpack Problem with an additional restriction on the number of items types

V. P. Ofitserov ; S. V. Smirnov

Čelâbinskij fiziko-matematičeskij žurnal, Tome 7 (2022) no. 3, pp. 267-276

Résumé

The task of forming a backpack with the maximum cost in case of the given restriction for the number of types of objects is considered. The choice of types is made from a finite set; the quantity of objects of each type is unlimited. When accounting additional restriction for the number of types of objects in a backpack (no more $d^*$ from $n$ possible types), the known methods of solution of the task about a backpack are ineffective. The method offered in the article relies on the idea of the dynamic programming of carrying out computation with use of results of the previous steps. On the first step of an algorithm the maximum cost of the created virtual backpacks in the case of their filling with objects only of one type is determined. On the second and the subsequent steps the maximum cost of the virtual backpacks in the case of their serial filling with objects of two types is determined, on the third — three types, etc. In the case of computation of the current maximum filling of the virtual backpacks the results received on the previous and first steps are used. It is proved that the offered method allows to receive a global extremum of target function and has smaller labor input in comparison with the known exact algorithms. The assessment of computing complexity of the algorithm is given.

Détail

Keywords: the task about a backpack, additional restrictions, dynamic programming.