Fractional Knapsack Algorithm

Description

Implementation of the "Fractional Knapsack" algorithm.

Pseudocode Modifications

My "value array" (denoted v in pseudocode) is actually an array of dictionaries, where each dictionary contains all relevant information for the given item. This allows me to store more data about the item, at a minor cost of:

• Some (negligible) extra memory space.
• An increased running time by a constant factor, to access the dict values.

This "value array" is also treated as a heap, using Python's built in "heapq" library.

Python Environment

This project is tested using Python3.7. Written using PyCharm. Tested with Pycharm 2017.2.3 and 2019.2 versions.

Creating a New Env

Most installations of Python3 will allow you to simply run python3.7 -m venv ./.venv to create a new Python3.7 environment called ".venv" at the current directory folder.

Once created, load this environment with source .venv/bin/activate on Linux or . .venv/Scripts/activate on Windows.

Third Party Libraries

• If any additional libraries have been used, then they will be found in requrements.txt at the project root.
• To install, load your local Python Environment and run pip install -r requirements.txt when at the project root.

Running the Program

Run the program via python ./main.py while at the project root.

Expected Output

None so far.

Running Tests

To run all unittests for this project, open a terminal and run the run_unit_tests.sh bash script.

For more information about testing, see the documents/testing.md file.

References

See the documents/references.md file.