Algorithms: Jeweler Profit Optimization (Bounded Knapsack)

For recurrence equations and proof of correctness, see report.pdf.

Usage Guide (Python)

*Not recommended. Python version is for verifying correctness of algorithm and testing on small inputs.*

jeweler_profit.py can be run from the command line as follows:

• python jeweler_profit.py - 1, this takes user input from the command line
• python jeweler_profit.py filename 1, reads input from file

Alternatively, we can also use pytest to test if everything works.

• Install pytest package using pip install -U pytest.
• Place test files in test_data folder. Either rename all test files to the form in*.txt or choose test files by changing the 7th line in test_jeweler_profit.py. For example, to test the code against a file test_data/test_sample.txt, change the 7th line to the following:
  TEST_FILES = ['test_data/test_sample.txt']

Note: I took this as an opportunity to learn Cython.

TODO: Add time benchmarks for Cython, Numba and Java.

Usage Guide (Cython)

• Install Cython: pip install cython.
• As mentioned here, run python setup.py build_ext --inplace to build the .pyx file containing cython code.
• Use run_bkp.py like jeweler_profit.py. Read the python usage guide above.