Skip to main content

Algorithms for Multiple Knapsack Problem (MKP)

Project description

mknapsack

Build Status

Algorithms for solving the Multiple 0-1 Knapsack Problem (MKP). Currently, only the MTM algorithm by S. Martello and P. Toth (1981) is implemented, which guarantees an exact solution. This repository contains a Python interface to C++ implementation of the algorithm.

Installation

pip install mknapsack

Example usage

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]

How should we assign these items to knapsacks in order to maximize the profit?

from mknapsack.algorithms import mtm

z, x, bt, glopt = mtm(profits, weights, capacities)
print('Total profit: %d' % z)
print('Solution: %s' % x)
print('Number of backtracks performed: %d' % bt)
print('Global optimum: %s' % glopt)

References


Jesse Myrberg (jesse.myrberg@gmail.com)

Project details


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.0.3.tar.gz (8.8 kB view hashes)

Uploaded Source

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page