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.

Bibliographie

[1] Martelo S., Toth P., Knapsack Problems, Wiley, 1990 | MR

[2] Bretthauer K. M., Shetty B., “The nonlinear knapsack problem — algorithms and applications”, European Journal of Operational Research, 138:3 (2002), 459–472 | DOI | MR | Zbl

[3] Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer Verlag, Berlin, Heidelberg, 2004 | MR | Zbl

[4] Kormen T., Leyzerson Ch., Rivest R., Stein K., Algorithms: creation and analysis, I.D. Williams, Moscow, 2013 (In Russ.)

[5] Hu H., Zhang X., Yan X., Wang L., Xu Y., “Solving a new 3D bin packing problem with deep reinforcement learning method”, 2017, arXiv: 1708.05930

[6] Massobrio R., Dorronzoro Diaz B., Nesmachnov Cánovas S.E., “Virtual Savant for the Knapsack Problem: learning for automatic resource allocation”, Proceedings of the Institute of System Programming of Russian Academy of Sciences, 31, no. 2, 2019, 21–32 (In Russ.)

[7] Kolpakov R.M., Posypkin M.A., “Upper and lower bounds for the complexity of branch and boundaries methods for knapsack problems”, Proceedings of the Institute of System Analysis of Russian Academy of Sciences, 32, 2008, 137–158 (In Russ.)

[8] Bellman R., Dreyfus S., Applied problems of dynamic programming, Nauka Publ., Moscow, 1965 (In Russ.)

[9] Bellman R. E., Dynamic Programming, University Press, Princeton, 2010 | MR | Zbl

[10] Kartushin D.Yu., Maksimenkova A.R., Ugolnitsky G.A., “Optimization of the quantity of applications with a given budget of innovations”, Modern economic: problems and solutions, 6:78 (2016), 20–33 (In Russ.)