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.10.tar.gz
(164.5 kB
view hashes)
Built Distributions
Close
Hashes for mknapsack-1.1.10-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3e8a2e0f2528602a4cdb7c9b35f9e59c7388705bf4b392c38d693be8613abf9 |
|
MD5 | eb773747f5f1b6ebc5249f8e29fa4aab |
|
BLAKE2b-256 | 82507aa35832075dc3d20137237de0a112549d4365b4ece77059cf35b3cf25fb |
Close
Hashes for mknapsack-1.1.10-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d14120041d00c50dad68fd4032348f3101ab0148567b03e24241ada1fabf4c3f |
|
MD5 | ec0bd4e72232ea23d22d7939aa1bb378 |
|
BLAKE2b-256 | af1ad7b0ff64048e099883dba7f7593202ba6292d499895d8e60738ba68f82bf |
Close
Hashes for mknapsack-1.1.10-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2b9422020205612564a62d1525dfe4c501e619798d9215feb27b74b9a16791a8 |
|
MD5 | c1a38a256d3efe69cd2d8c7c5a426baa |
|
BLAKE2b-256 | 5f34dc6d8fff66fe769944ebc63965a1add6cda4116e4b88e3f01f024692bac4 |
Close
Hashes for mknapsack-1.1.10-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e8464806a01a21e1660fbd6f6426c448a5c3fcaadf29463e87f7244092ace6aa |
|
MD5 | 336a19da784564db25173df4dc83357a |
|
BLAKE2b-256 | 13e900dab99041568e1afa28b32669b2d46baa56ac7a5c72e35d911481328436 |
Close
Hashes for mknapsack-1.1.10-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8368c2682df759ce97afe7d3a2d39e11f8e0a8ade9a1ee4ed6336b05a6e07a54 |
|
MD5 | c35bd74a63257dd99bac30e481734b3f |
|
BLAKE2b-256 | f366be345ad1303c6b37ca81a7fef93d8c854743a734eb28697893c6b7443f98 |
Close
Hashes for mknapsack-1.1.10-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 735683e555e7084d0276229191c227da0f11e40d8a3530394a6ad6b3786907d3 |
|
MD5 | 42baf2d6b08cf2528e7cd5e7ff5aeef9 |
|
BLAKE2b-256 | edf4e413b4878b19f695746121fd45e51cca762571493c85c1e629bef85ecb61 |
Close
Hashes for mknapsack-1.1.10-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7dfd0b75078a8ff4cadb1c7c357212aace54ce5335b4029d8ca9e8d274124d9a |
|
MD5 | ffbc3fbd10b345de870f50c5e80cef17 |
|
BLAKE2b-256 | f80b285a00e7d4f7a5db8a04d7164bc0f990e6ce783e5f0a2a9703ffcdae8856 |
Close
Hashes for mknapsack-1.1.10-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 01fe587ccbd49d4389697187242c87b0776966dd0cfad5f07cbea5915e0baf75 |
|
MD5 | e303f380430311dfaaabca2e59cd0bf7 |
|
BLAKE2b-256 | 8377670057f8b416d0d29763a6a458c26f7a8b174cd8b709f28a304861938c67 |
Close
Hashes for mknapsack-1.1.10-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f61444fce531da7909ad7dac7bd64c5b67afcf0b42969510b6d9226ad22267ba |
|
MD5 | 7584b55746dcb06bb6a3ce3cbb81f44d |
|
BLAKE2b-256 | 64697be91b4d2cb5886bcc648cc17162fd4b90ff9249a487ac353528432bf54a |
Close
Hashes for mknapsack-1.1.10-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9335aa46d835f259db29d3a0649e24c05773c2b62f4a2197e17b97620f9da4a |
|
MD5 | 9156e41da231223cbd0525cc2789f811 |
|
BLAKE2b-256 | 391bb9fda32ab4a89669cf30a4a785ef627220c68246442829e2c3762f981e39 |
Close
Hashes for mknapsack-1.1.10-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9acbe646d8598ab3884e154faa31c5d62d6987e57a26045792894bee08400b3 |
|
MD5 | c4c443c69b87fcd3348ff4b16faa239e |
|
BLAKE2b-256 | caa1248d99f17ace862e271d2611baa9a5e856ed7300a63d1f6a7a88cf45336d |
Close
Hashes for mknapsack-1.1.10-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebcff149c6b79630bc502307b3e231d494c20650d09e4b6ae747dff07343bc58 |
|
MD5 | a243c922dc04c0297547842cadddc2aa |
|
BLAKE2b-256 | f959c53deb0767db1dc98dc789a68a9517c7963f3deabac42a17c04b76f2d23a |