The Knapsack Problem (KP) is a combinatorial optimization problem, where one wishes to fill his bag with enough items satisfiying his constraints ie weight and value. An example can be where one travels to Dubai and has an unlimited card, but the only issue is that economy and business class only allows 48Kgs non negotiable per customer in the time of coronavirus 2021.
Two problems are considered:
- Linear knapsack problem (LKP) - the objective function and constraint(s) are linear. This signifies that the constraint are not complex and one can follow a Greedy approach to solve this problem. The other extension of this problem is Polynomial Time Approximation Algorithm (PTAS) which is well explained in (4).
- Quadratic knapsack problem (QKP) - has quadratic objective function and it is an extension of the linear Knapsack problem where there are additional terms in the objective function that describes extra profit gained from choosing a particular combination of items. The essence of this variation of the knapsack problem are the pre defined group of items that need to be added to the bag, while also satisfying the other constraints of the user and in the end applying the greedy approach (maggie on the image above) checks the remaining capacity and adds the items most suitable.
This project was done using python (jupyter-notebook), and in the Project folder there are 3 other subsequent folders namely:
- src - or source code where the different implementations of the knapsack problem are located.
- pdf - where summary of the work is present.
- img - has the visualization gif used in the repo 😁.
To run the implementations located in src simply select the '.ipynb' file.
Note: The complete report for this project will be made avaliable for the time being.
-
Discrete Optimization lecturer @ Wits
-
Github and google
- Repo owner Neil Fabião -> @neilfabiao ✌🏾