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.12.tar.gz
(164.3 kB
view hashes)
Built Distributions
Close
Hashes for mknapsack-1.1.12-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3680d40d6e30a3f887448725b9f3f2ce714812f18ddb869efc3a2fe29f4f0871 |
|
MD5 | 32ac8308811652eebc99704c31732c90 |
|
BLAKE2b-256 | 2730fefe5f5cdb4e8887673d025261de509b8a7dbbd4e9dd80b1b77b87756161 |
Close
Hashes for mknapsack-1.1.12-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 03e1733b029efd38114f05afa9286a932bf236001f48ae2c24c3d4571db4a5ac |
|
MD5 | 80969a515618e6828577c49dc3efd3cd |
|
BLAKE2b-256 | 2b30e9db087389a695483c84e875e4de2e31012cc615425bcd686d852112072f |
Close
Hashes for mknapsack-1.1.12-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4dea5a2b5bf41deb3cbbcfca7bd8b185f21b65b4bb20a158f008e7119d4f9a99 |
|
MD5 | e8e6d010e6e5f9cb10c73c030daef350 |
|
BLAKE2b-256 | e1ac5b78df00775420f5d168a03bae38cdd07e0a165b990f1ea8f889b5a5b4e2 |
Close
Hashes for mknapsack-1.1.12-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9163a736d552b2b5bc8f8a46e3755573ef937338f9aebfd92590346160ffcdb8 |
|
MD5 | aad730b358940f1499b7549073a85073 |
|
BLAKE2b-256 | 2a76dc20c258aa83ed6bdea569d3a1ed05b1826e197180ed87832f0c4f0b9cf5 |
Close
Hashes for mknapsack-1.1.12-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c3cca52d794da94ab3829aedb356951072cdaeec4f99d9aa4338d828711281c |
|
MD5 | fc41e6a622acd1b753eba5327a657c5b |
|
BLAKE2b-256 | 8d175848a0ec5c6457627383b11be2fd2dd52526d9c276795f959495da94b25d |
Close
Hashes for mknapsack-1.1.12-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e4cef34b7aceb83384f0a3742b08a215dd36c290e65b67ca11e0957e3769567 |
|
MD5 | bc7f63fc496a8ff032ccf6f3da58a249 |
|
BLAKE2b-256 | 3eaecce565230b57f6eb2688a503427e870bac44d7de3807eaa3d09cc009f5db |
Close
Hashes for mknapsack-1.1.12-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 76485a4bbb0d63775be99d0fcb49273613abde77df044a1c69144a2ab11a1e6f |
|
MD5 | ef0450a8a329a17f724ab10eb353a850 |
|
BLAKE2b-256 | 6dcad7177c0420aec1564b79857b4a27d725d4aedccb7dbb8cf50af49ef14feb |
Close
Hashes for mknapsack-1.1.12-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d67767a49e69baad5a87169d5d71d37b0bbc561e8cb99da56b93abef153ab285 |
|
MD5 | e90f25d1d22253a7291bde634de18ac7 |
|
BLAKE2b-256 | ec6b53f9bee7707f17f5761bb2638a1879c4410c3b26a78bf4bf776d8e94a389 |
Close
Hashes for mknapsack-1.1.12-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e28a787d79e17d13280decded3ae7d7d354216b28355adc49dcfe57c74a75e61 |
|
MD5 | bd4b4bde876f00b8f88dac9f32cbe7fc |
|
BLAKE2b-256 | 1b9c25a9caa7806a644c195c2defc370fb7fa946a20b32f05b2d470bb2bc29cc |
Close
Hashes for mknapsack-1.1.12-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90792822fcda970b561b7fbbc9abf29309a090408ef6c45a594d76dda5bfbac9 |
|
MD5 | 76aeb06ed06f444345bf9f6e92bd6787 |
|
BLAKE2b-256 | 8252fc8f44bcf487ca96382160aeb6d1356295390a65c35f8f9ee54933f6f5f9 |
Close
Hashes for mknapsack-1.1.12-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e462d94e8e9e28b6d4be21e581ff64ac48741a633e358a89030acd755121a076 |
|
MD5 | 3110a47874ea2ad6c5dfbc49959912f0 |
|
BLAKE2b-256 | aa371739e4f3231f32cdb4ffca9a27cc0e873902d5d6f1da49707b4825ba44d0 |
Close
Hashes for mknapsack-1.1.12-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 944db401d2dbada8ea3a44b8f57e49ee05e5ac3f36488b518b49ba47c9b773df |
|
MD5 | bf1a6eb7a3f291d4313f4aad81bdc219 |
|
BLAKE2b-256 | 9c5bac42d7865c8bcda3abc708b975c3154b94c595d894cf7567923b0ff18183 |