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.
Quickstart
Installation
pip install knapsack_python
or
git clone https://github.com/python_knapsack
cd python_knapsack
python setup.py install
Use
All functions live in the knapsack_python module.
Example
Dependencies
numpy
TODOs
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
0.1.0
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
1 maintainer
Metadata
1 maintainer
Release files for knapsack_python 0.1.3
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| knapsack_python-0.1.3.tar.gz | 387.9 kB | Without provenance | Details for knapsack_python-0.1.3.tar.gz |
Release files / knapsack_python-0.1.3.tar.gz
| Download URL | knapsack_python-0.1.3.tar.gz |
|---|---|
| Size | 387.9 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
2693a8dbfb9cca5024e5d8b0129f1ee135e8ffe59213192d994292ff064a3d76
|
|
BLAKE2b-256 checksum How to use checksums |
9d975c2c5bcf18bc2bc9f02defcba791713a45062ddd8b5100a7a5dbd8dc8985
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
Security for knapsack_python 0.1.3
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.
