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
or
- git clone https://github.com/python_knapsack
- cd python_knapsack
- python setup.py install
All functions live in the knapsack_python module.
- numpy
- 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