Solving knapsack and bin packing problems with Python
Project description
mknapsack
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
- Knapsack problems: algorithms and computer implementations by S. Martello and P. Toth, 1990
- Original Fortran77 source code by S. Martello and P. Toth
Jesse Myrberg (jesse.myrberg@gmail.com)
Project details
Release history Release notifications | RSS feed
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.8.tar.gz
(164.5 kB
view hashes)
Built Distributions
Close
Hashes for mknapsack-1.1.8-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9318ba9de7ecaa538048420593b9b29466b11022e66ddb47d8508fb7c66e0bce |
|
MD5 | 6895ef118dd1af6ecb4228e5d3c881b5 |
|
BLAKE2b-256 | b0f12e2c130485e558eff6962a607e309d691ec7e2dde0779c0fdd7d392eb1f0 |
Close
Hashes for mknapsack-1.1.8-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8cecdc53dbd38bbe2be45b230a7933704d675fea3d8b8443f0ba1fceb9a0114e |
|
MD5 | 6c5c7c9ecca378c81170491520c1c3b9 |
|
BLAKE2b-256 | d91b105f576bd7c4159e60edf790467aba4e84b6cc8747589efc0a29f7959be5 |
Close
Hashes for mknapsack-1.1.8-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1e28aa15b1874b7f36507b49c64b0a658ee0244cdfc92459224e0fd37b2ddd08 |
|
MD5 | f71896e07adde800a7bda3a598d57ce2 |
|
BLAKE2b-256 | 5120086b3ff6df0e85bb2452d4c4c6ce91920ae3a6c4e596f0f1915a38f6e4fb |
Close
Hashes for mknapsack-1.1.8-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ba9e92c6b54004ef7974c2d90c60eacc633d8bd30b9bdcce6dce49266d2f394c |
|
MD5 | 11d158dd0aeb473afece5ae6c05778e1 |
|
BLAKE2b-256 | 491f4fac10922c340e0fff256620352204977a7a37693787ac633717d83f0e4f |
Close
Hashes for mknapsack-1.1.8-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bacb136e4d69300e649d3a3b2d61b64dbf967247e91511b0d347ff4ad55dbcfe |
|
MD5 | 3f3d2972620b1addc165b880ae45df4f |
|
BLAKE2b-256 | 09f90a73ba6d7c3b37f991ffc3fac49732ef6aeac418b21fa718f88ef5c6864f |
Close
Hashes for mknapsack-1.1.8-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9a65f8b8cde25c3f1327745e8dc08270ea699d0d96e330b8f6d1d336b1865012 |
|
MD5 | 2251f9a2f97474c4cdeeef36b7891650 |
|
BLAKE2b-256 | 519189d116227789b476919c361683abdfc101c15ae3d5bf460b1b47b3218c09 |
Close
Hashes for mknapsack-1.1.8-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a861914f08662e3d19186bac166ad382acf31c5afa48d6ad2e3e5f348f652a4d |
|
MD5 | 3fa85d1792e5432962a1a4b9258bf8b5 |
|
BLAKE2b-256 | 2bccaee762cc8ff05025019774cfb5da16e5205501e6745fd8da5ce442b43c22 |
Close
Hashes for mknapsack-1.1.8-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a7b9dd9bc545af44a7881f4291a83a7a58e532258fb7d4e2aa466390fbc4efd |
|
MD5 | 59188412a25647374eeeca9cad3deae7 |
|
BLAKE2b-256 | 69c2121784380ee2dae56142300e97c862f94cb18735f30c406ec5d7884bde94 |
Close
Hashes for mknapsack-1.1.8-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3c7b9d40b4bd0f1d4be56a2d5f7a50abf595174113d389d434bd03e49afd978 |
|
MD5 | 44660702a3df44f1473ae9ee17232de9 |
|
BLAKE2b-256 | 374489865e4e7f09edf64ac283581db71d94bc0e3042dbcdd0b819fcc0a824d2 |
Close
Hashes for mknapsack-1.1.8-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7fa1a86900317ad60a90dc595055501ce073bd2c4e4d8de84e70476484af018e |
|
MD5 | 63b87d7b378a7f6efc44f82dd32bf90c |
|
BLAKE2b-256 | b4f6637c36bbc46665afdaab0257313d1bdfa19d42060f0983e94afd11763224 |
Close
Hashes for mknapsack-1.1.8-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5163bb704913f5ecfdc3ebcfac61d9c7f01a7391b5471fe984a110d2175f8818 |
|
MD5 | e4187ddc54ce70eb8c5d7034ca87483a |
|
BLAKE2b-256 | 7ae39385f94d61b5e5204f376d42634847c454d94ee7bd1bc8fba34892b613ce |
Close
Hashes for mknapsack-1.1.8-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7093f406b8de6e8d59c12dac05c32dc8e137ab959cb3f5b69be2b6306f31ad1a |
|
MD5 | 66dbbd64609634c20559b94beff9d9b6 |
|
BLAKE2b-256 | 369ef56fcdb2131361838c075ae2dbca6a8ac784a0edef4438321a58dcba39c9 |