A GPU-based DP algorithm for solving multiple instances of the knapsack problem - Lemos, Dayllon V. X.; Longo, Humberto J.; Martins, Wellington S.; Foulds, Les R. (Anais do Simpósio em Sistemas Computacionais de Alto Desempenho (SSCAD); 2023: Anais do XXIV Simpósio em Sistemas Computacionais de Alto DesempenhoDO - 10.5753/wscad.2023.235875, 2023)
The knapsack problem is a classic and fundamental optimisation problem that serves as a subproblem in various optimisation algorithms. Thus, it is of great importance that we manage to solve several instances of the knapsack problem in a fast and efficient way. In this work we present a parallel algorithm, based on dynamic programming, that can take advantage of parallelism as more knapsacks need to be solved. The algorithm makes use of fine-grained data parallelism and is easily mapped to GPU accelerators. Extensive experiments with diverse datasets demonstrate the superiority of the proposed algorithm, achieving relevant speedups compared to a serial algorithm.