Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

Solves a variety of knapsack problems

Project description

Build Status

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



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


  • 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

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for knapsack_python, version 0.1.3
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 hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page