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.11.tar.gz
(164.2 kB
view hashes)
Built Distributions
Close
Hashes for mknapsack-1.1.11-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4457580bc784f8d8d0567dc56e4edd9b1225671b8d5f5f170c0ed5fe991b09d9 |
|
MD5 | 9791575fd4366126d1a07a43bac0327e |
|
BLAKE2b-256 | 914d512f915ab8ff78dc43ccdcadcf75bce81bad58474d2c4772946ebf3348d2 |
Close
Hashes for mknapsack-1.1.11-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f0cc5d2426b825905c4d78afb0482aea83301e4f9e761faa6a2a6d7e1da5803a |
|
MD5 | 5e9f4f132e47f0a699ffdb9480c22ccb |
|
BLAKE2b-256 | b45c05cd40a1e220366c35cdcd40a5c38845a2cb553d8f4234fe0518f3e85e8a |
Close
Hashes for mknapsack-1.1.11-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 24452459ec35aa44373936cd836f7be5d08bc87581665edc7c6077c3e0888402 |
|
MD5 | 30db85de314adabcf19a471dbdbd29ca |
|
BLAKE2b-256 | 7aa358c81c66d8a49eea89f1ca98019d5c8c7cfaada98b185f903192252fbb55 |
Close
Hashes for mknapsack-1.1.11-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9ed8405dec03a6cc09c1447de44614ece410b3b733c6c0c2c572e96c7f73dd67 |
|
MD5 | f0b62f0d8d49b6f9cfcf175175c30239 |
|
BLAKE2b-256 | f01c3e99ac5922f195ed06f4e35e204b5e0a2d084f0fcf4f16562a282c104580 |
Close
Hashes for mknapsack-1.1.11-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ac9d87aecb48c06846525c7eef8e7593e3427a606466c2df85b05c12366dd839 |
|
MD5 | 553b6ce20c103e6956fa9ff6ff6a0a50 |
|
BLAKE2b-256 | ad505dafbcbe93283567e1d1edb611e5dae0d364edc8f8f92141a5539da701d1 |
Close
Hashes for mknapsack-1.1.11-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 11eda42d99e2a41b81a20bbbde6f71744826631d2df61a1d8af9eb9b2c4b5f76 |
|
MD5 | 4e8e8d368a940f4627d99bdf2c021b61 |
|
BLAKE2b-256 | 2a05c7b75f5301cc45f4702b60c83256e222934c54a44f48248f3d3d232f272b |
Close
Hashes for mknapsack-1.1.11-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 710470ad1ee196f02063b049e948ce2da4f2be87ecf8be0d88b15cc0e528fb68 |
|
MD5 | 307bd745cf6dcef768ec4c96c254211c |
|
BLAKE2b-256 | 7abb0881454a878777fdce8d473b2780f7f4c20110b24668604bee7ff767f084 |
Close
Hashes for mknapsack-1.1.11-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dd5a55221d566b59f6006dff1c7b17c2a062269b66afc19b0fb36bdfc1db9cd2 |
|
MD5 | 8b2e49495ffbfea2e45109a4d81c4ac3 |
|
BLAKE2b-256 | f0de2716ba2b2a4300a8a14df9691af9c6d9a0c488e89b3c3c27e4366fa64dfc |
Close
Hashes for mknapsack-1.1.11-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b56711a1b73a58c4d3a890095e980e565035a3706caceab0911506db15a3b23 |
|
MD5 | 72d8127b99bc5de22c7538089d882f02 |
|
BLAKE2b-256 | 94ffc7518c970903a513b150aeb2accf69f64976ba662c7e1460e1cdc7932426 |
Close
Hashes for mknapsack-1.1.11-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 70c79f07dc5d73a624ac2f79bd70079e5be29e354f7c8916488361ef00cc1b1e |
|
MD5 | 6023b75dfd878ec8d1e44714f99739ca |
|
BLAKE2b-256 | 048c368ea8c98665a75edaceac23da47635cb98f5439f793df182c368c61bad4 |
Close
Hashes for mknapsack-1.1.11-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b99ce93470afaf828ca451e3afb35d3def76d1626f7db06ddce05380ec6b19d5 |
|
MD5 | 9372c32168493eb04c524358f087ca22 |
|
BLAKE2b-256 | 805ff2abda45a468d321cbb59f62a1af1d0459e3e6c02bb678351546938ca519 |
Close
Hashes for mknapsack-1.1.11-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a436dd6f420d4702e6eb7e1a3a36ca4f1e4c14a286e6a006584a12f94835bc0 |
|
MD5 | c383e67ce53d20a90247d3cfb4dbcb5c |
|
BLAKE2b-256 | 7a9d3288762edb353f2c98d238630eda5df7b4ae95acf6ab87b9462df5ac51ec |