by Avo-Catto
This desktop application uses PyQt5 and I wrote it for my scientific essay in school where I treated the knapsack problem.
The knapsack problem is an optimization problem of combinatiorics and belongs to the np-complete problems. The problem is that you have a backpack with a maximum weight, which should be filled so that the maximum weight is not exceeded and at the same time contains the greatest possible value(€).
First you need to copy the git-repository and install the requirements. Then you run the run.py file, which opens the window and creates a file for the items. To create a list with random items run the item_creator.py.
I used simple algorythms with following benefits:
- Recursive Algorythm -> very slow, but best precision
- Greedy Algorythm -> very fast, but most time bad precision
- Smart Greedy Algorythm -> fast, and nearly precision like the Recursive Algorythm
If the window freezes after starting an algorythm, it didn't crashed. It only calculating and could take a while pretending on your selection.