Skip to main content
Python Software Foundation 20th Year Anniversary Fundraiser  Donate today!

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.

Quickstart

Installation

  • pip install knapsack_python

or

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

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

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page