Solves a variety of knapsack problems
knapsack_python: Solves a variety of knapsack problems
This package is a collection of solutions to various knapsack problems. In particular, it has solutions to:
- the 01 knapsack problem,
- the 01 multi-knapsack problem (MKP),
and potentially more in the future. A good introduction to these sorts of problems can be found on Wikipedia (here and here). Additionally, it contains functions I’ve found useful in my work. One such function is assign_all, which assigns all items to one or more knapsacks while trying to adhere as best as possible to the capacities of each knapsack. Most of the solutions are a direct translation of the solutions given in Silvano Martello and Paolo Toth excellent book *Knapsack Problems: Algorithms and Computer Implementations*.
The implementations of these solutions are all written in C++ and wrapped in Cython for use in Python.
- pip install knapsack_python
- git clone https://github.com/python_knapsack
- cd python_knapsack
- python setup.py install
All functions live in the knapsack_python module.
- More comprehensive documentation
- Implement other knapsack-related problems such as:
- 0-1 Knapsack Problem (really a special case of MKP)
- Multiple-Choice Knapsack Problem
- Bounded/Unbounded Knapsack Problem
- Change-Making Problem
- Generalized Assignment Problem
- Initial release with implementations of:
- The MTHM algorithm for solving the multi-knapsack problem
- A function to force assignment of all items while trying to respect the knapsacks’ capacities as much as possible
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size knapsack_python-0.1.3.tar.gz (387.9 kB)||File type Source||Python version None||Upload date||Hashes View|