The multidimensional 0–1 knapsack problem solved using a greedy algorithm.
This tool was born from nessecity and can be used to determine any combination of balanced knapsacks based on an object's value.
note: Although the following is not the only use for this tool, this was the original use case.
You are holding a Beer Olympics, the goal is to create teams that are equally matched(or as close as possible) to ensure each team has a fair chance. Each player has a rating for each event, the ratings add up to the player's overall value. Implement a greedy algorithm to solve the multidimensional 0–1 knapsack problem.
Details:
- Each team has 3 players
- there are 5 teams
- Each player has a total value that is calculated by the given file inputs
Below are the details about each player. The rating for each player is separated by a semi-colon, all ratings should be summed to find a player's value.
-- Name; Case Race; Beer Ball; Flip 50;
Nicole;1;2;2;
Jenna;2;2;5;
Krendan;4;3;3;
Dylan;4;3;3;
Luke;5;5;3;
Jason;5;4;3;
Brendan;5;4;3;
James E;3;3;3;
Aidan;3;4;5;
Daniel;4;5;4;
Maya;3;3;5;
James C;3;3;3;
Kayvan;3;2;2;
Steph;3;2;4;
Kevin;3;3;3;
For installation just run the make target
make
mkp -h
Usage: __main__.py [OPTIONS]
Options:
-h, --help Show this message and exit.
--version Show the version and exit.
-e, --examples Generate example files
-k, --knapsacks INTEGER The total number of knapsacks to fill [required]
-c, --capacity INTEGER The capacity of each knapsack [required]
-f, --file PATH Path to objects for knapsacking [required]
the object input is provided via a file, the format for which is defined below.
Comment Deliminator: --
-- Object Title; Event 1 Rating; Event 2 Rating; ... Event N Rating;
To get all necessary dependencies run:
make init
Then enter a new pipenv shell via:
pipenv shell
Now to run the cli from source run
python3 -m mkp