Recovering Beam Search for the 0-1 Knapsack Problem with Forfeits
Ghassane Ben El Aattar
Recovering Beam Search for the 0-1 Knapsack Problem with Forfeits.
Rel. Federico Della Croce Di Dojola. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2024
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (722kB) | Preview |
|
|
Archive (ZIP) (Documenti_allegati)
- Altro
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (3MB) |
Abstract
The Knapsack Problem is one of the well-known problems in the field of combinatorial optimization, studied for over a century. It is a problem with a very intuitive construction, but it has numerous applications in various fields such as cryptography. There are several variants of this problem, such as the 0-1 Knapsack Problem, the Multidimensional Knapsack Problem, and others. In this thesis, our goal is to develop a solution for the 0-1 Knapsack Problem with Forfeits (or Penalties). This problem is a particular case of the 0-1 Knapsack Problem in which there is a reduction in profit when certain pairs of items are taken into the knapsack.
This problem is difficult to solve, as it belongs to the class of NP-Hard problems
Tipo di pubblicazione
URI
![]() |
Modifica (riservato agli operatori) |
