Skip to main content

Solving knapsack and bin packing problems with Python

Project description

mknapsack

CICD Build 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
  • Change-making problem: MTC2
  • Bounded change-making problem: MTCB
  • Generalized assignment problem: MTG, MTHG
  • Bin packing problem: MTP
  • Subset sum problem: MTSL

Documentation is available here.

Installation

pip install 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 available 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)

Change-Making Problem

from mknapsack import solve_change_making

# Given ten item types with the following weights:
weights = [18, 9, 23, 20, 59, 61, 70, 75, 76, 30]

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

# Fill the knapsack while minimizing the number of items
res = solve_change_making(weights, capacity)

Bounded Change-Making Problem

from mknapsack import solve_bounded_change_making

# Given ten item types with the following weights:
weights = [18, 9, 23, 20, 59, 61, 70, 75, 76, 30]

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

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

# Fill the knapsack while minimizing the number of items
res = solve_bounded_change_making(weights, n_items, capacity)

Generalized Assignment Problem

from mknapsack import solve_generalized_assignment

# Given seven item types with the following knapsack dependent profits:
profits = [[6, 9, 4, 2, 10, 3, 6],
           [4, 8, 9, 1, 7, 5, 4]]

# ...and the following knapsack dependent weights:
weights = [[4, 1, 2, 1, 4, 3, 8],
           [9, 9, 8, 1, 3, 8, 7]]

# ...and two knapsacks with the following capacities:
capacities = [11, 22]

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

Bin Packing Problem

from mknapsack import solve_bin_packing

# Given six items with the following weights:
weights = [4, 1, 8, 1, 4, 2]

# ...and bins with the following capacity:
capacity = 10

# Assign items into bins while minimizing the number of bins required
res = solve_bin_packing(weights, capacity)

Subset Sum Problem

from mknapsack import solve_subset_sum

# Given six items with the following weights:
weights = [4, 1, 8, 1, 4, 2]

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

# Choose items to fill the knapsack to the fullest
res = solve_subset_sum(weights, capacity)

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.9.tar.gz (164.5 kB view hashes)

Uploaded Source

Built Distributions

mknapsack-1.1.9-cp311-cp311-win_amd64.whl (793.2 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

mknapsack-1.1.9-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.8 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

mknapsack-1.1.9-cp311-cp311-macosx_10_9_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

mknapsack-1.1.9-cp310-cp310-win_amd64.whl (793.2 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

mknapsack-1.1.9-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.8 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

mknapsack-1.1.9-cp310-cp310-macosx_10_9_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

mknapsack-1.1.9-cp39-cp39-win_amd64.whl (793.2 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

mknapsack-1.1.9-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.8 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

mknapsack-1.1.9-cp39-cp39-macosx_10_9_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

mknapsack-1.1.9-cp38-cp38-win_amd64.whl (793.2 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

mknapsack-1.1.9-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.9 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

mknapsack-1.1.9-cp38-cp38-macosx_10_9_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

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