Skip to main content

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


Release history Release notifications

This version
History Node

0.1.3

History Node

0.1.2

History Node

0.1.1

History Node

0.1.0

Download files

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

Filename, size & hash SHA256 hash help File type Python version Upload date
knapsack_python-0.1.3.tar.gz (387.9 kB) Copy SHA256 hash SHA256 Source None Oct 9, 2017

Supported by

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