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.7.tar.gz
(164.2 kB
view hashes)
Built Distributions
Close
Hashes for mknapsack-1.1.7-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85ddcc11643518cac87879577b7b8af5e3160edb6c6d208f287841546990904f |
|
MD5 | eed1d6f3704cf3739022758fe83e4a04 |
|
BLAKE2b-256 | 56282fc533fb76893eb1999876754c225f82dfa3bc0970023a5a77e1b8955ab2 |
Close
Hashes for mknapsack-1.1.7-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4b7607d15279443aa7e38fd4573ae01434565a71bf30b4e00d5ac44ba5b501bd |
|
MD5 | b26eb257e3efa889243c299c51666fda |
|
BLAKE2b-256 | 76134b1a872444c032c2815c6810382d7521350fa3a8796ffa94d2c165234e01 |
Close
Hashes for mknapsack-1.1.7-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 929965dbc5e5f817a24420d44d9b956b21154bf5709d4445dd3f4809c7c89550 |
|
MD5 | 3cf91a667008d965bf1d42ba8c9223d1 |
|
BLAKE2b-256 | a453d6b47a83155f4b6c4f73a9bcb776f763317447426bf0fad07450fef0ce53 |
Close
Hashes for mknapsack-1.1.7-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a9c422e1ee2e2c0ef1b913de00849b50fcb1d96fde264f1bd14e5d355507f9a |
|
MD5 | 74be33d32ec2c566a11e55be7dbc6649 |
|
BLAKE2b-256 | 3e0f10f823f789a381e57291b0175e6fe8addf1bd483432329fdb14cc91d38ba |
Close
Hashes for mknapsack-1.1.7-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 697c55c8c71df99e63edc9e6d57dca505dad369f64a0e566a710d3aaeb643257 |
|
MD5 | b67398f1b30e4faf44ace8ac331fd923 |
|
BLAKE2b-256 | 492a32e71517924c6e042cd14fdfdf828c140f87d9eaf7f3c362f92774782019 |
Close
Hashes for mknapsack-1.1.7-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e2cadb22645393370137212da93393aa6997608486cf7f791693df6d28d76850 |
|
MD5 | 16ed395030aa4e2b227e66a05cd953ae |
|
BLAKE2b-256 | c5431550f0401003aa786543c4f7a9b3ddc73e863ccd3965c71ce1f920750323 |
Close
Hashes for mknapsack-1.1.7-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 414c7395afa7272746c5b15d1ba3c52a63d517c30bdce6cc3623727b8c636cae |
|
MD5 | 3e04338d06fc6f273c5661c155dedaf4 |
|
BLAKE2b-256 | 70737fa44b881371d1b268b70200285667c2d1222d595844715806f01fb823e8 |
Close
Hashes for mknapsack-1.1.7-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4bc7964a47a6b58e27815c1fa141852cd4ba7ceba44c377a40ff934645a70b8b |
|
MD5 | f7bcb04e9d1ed55da7dc5ee8e8db1862 |
|
BLAKE2b-256 | 1314bff7f88de0d7d3b6e8da42c0fa2075b26d8f6790ab338d7fcf726685fe42 |
Close
Hashes for mknapsack-1.1.7-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 06db1ab8a1d38c3f0d39f7ecdf227dc47545c13112c6ac334c4a5f0c37e3dbfc |
|
MD5 | 361e5674247cb97ec698b1c0cc89b51f |
|
BLAKE2b-256 | d5c159afc959b80d64052aed6d3a5390661968909d7dc3080de8ab6a083d6e2b |
Close
Hashes for mknapsack-1.1.7-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 727a3349ef7216ee9324bd5cd26f10e3cf83e252e8e98a30a2db3b827bf36713 |
|
MD5 | 3db43f840cae5a3f10468c6559b44c2d |
|
BLAKE2b-256 | c0966c1a36429a108f8ca7f340675c7648049caf194a60d21b0a5a3d4b69cd32 |
Close
Hashes for mknapsack-1.1.7-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5dd8444cddadf1ba3cebf61f258dd882dc8af3acd4cc68f4ce274c339a680eb |
|
MD5 | 652b601ff5650523590d061f5fe94bbd |
|
BLAKE2b-256 | 341273afedf0f3be3d7ef9ffebbbc4cd8438a58f6d5b74537edadf0c6967c0bb |
Close
Hashes for mknapsack-1.1.7-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bbfe7ff0cb7b8fa31eff033740a1dcd6b4b043432cd306fc1d4b331f18454c16 |
|
MD5 | 5f91c18d90081f287f33561bf4d41a75 |
|
BLAKE2b-256 | 78c008c0b9d4aa4b90e73b837b5fa1ca66b4ac2ddda50235dbe672c57e36df85 |