Skip to main content

Solving knapsack and bin packing problems with Python

Project description

mknapsack

CICD Documentation

mknapsack cover

Solving knapsack problems with Python using algorithms by Martello and Toth:

  • Single 0-1 knapsack problem: MT1, MT2, MT1R (real numbers)
  • Bounded knapsack problem: MTB2
  • Unbounded knapsack problem: MTU1, MTU2
  • Multiple 0-1 knapsack problem: MTM, MTHM

Documentation is available here.

Installation

  1. Install Fortran compiler, if you don't already have it

    • MacOS / Linux: brew install gcc
    • Linux / Windows Subsystem for Linux: sudo apt-get install gfortran
    • Windows (experimental):
      • conda install -c conda-forge m2w64-toolchain_win-64, or
      • Install MSYS2 and pacman -S --needed base-devel mingw-w64-x86_64-toolchain
  2. pip install -U mknapsack

Example usage

Single 0-1 Knapsack Problem

from mknapsack import solve_single_knapsack

# Given ten items with the following profits and weights:
profits = [78, 35, 89, 36, 94, 75, 74, 79, 80, 16]
weights = [18, 9, 23, 20, 59, 61, 70, 75, 76, 30]

# ...and a knapsack with the following capacity:
capacity = 190

# Assign items into the knapsack while maximizing profits
res = solve_single_knapsack(profits, weights, capacity)

If your inputs are real numbers, you may set parameter method='mt1r'.

Bounded Knapsack Problem

from mknapsack import solve_bounded_knapsack

# Given ten item types with the following profits and weights:
profits = [78, 35, 89, 36, 94, 75, 74, 79, 80, 16]
weights = [18, 9, 23, 20, 59, 61, 70, 75, 76, 30]

# ..and the number of items for each item type:
n_items = [1, 2, 3, 2, 2, 1, 2, 2, 1, 4]

# ...and a knapsack with the following capacity:
capacity = 190

# Assign items into the knapsack while maximizing profits
res = solve_bounded_knapsack(profits, weights, capacity, n_items)

Unbounded Knapsack Problem

from mknapsack import solve_unbounded_knapsack

# Given ten item types with the following profits and weights:
profits = [16, 72, 35, 89, 36, 94, 75, 74, 100, 80]
weights = [30, 18, 9, 23, 20, 59, 61, 70, 75, 76]

# ...and a knapsack with the following capacity:
capacity = 190

# Assign items repeatedly into the knapsack while maximizing profits
res = solve_unbounded_knapsack(profits, weights, capacity, n_items)

Multiple 0-1 Knapsack Problem

from mknapsack import solve_multiple_knapsack

# Given ten items with the following profits and weights:
profits = [78, 35, 89, 36, 94, 75, 74, 79, 80, 16]
weights = [18, 9, 23, 20, 59, 61, 70, 75, 76, 30]

# ...and two knapsacks with the following capacities:
capacities = [90, 100]

# Assign items into the knapsacks while maximizing profits
res = solve_multiple_knapsack(profits, weights, capacities)

References


Jesse Myrberg (jesse.myrberg@gmail.com)

Project details


Download files

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

Source Distribution

mknapsack-1.1.2.tar.gz (154.8 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page