# Algorithm Testing: Knapsack A simulation comparing **Brute Force** vs **Dynamic Programming** approaches to the 0/1 Knapsack problem, framed as a "study time allocation" scenario: given a set of study topics (each with an hour cost and a grade-boost value) and a limited number of study hours, find the subset of topics that maximizes total grade boost without exceeding the hour budget. ## Why two solvers? | Solver | File | Time Complexity | Notes | |---|---|---|---| | Brute Force | `src/knapsack_brute_force.py` | O(2^n) | Enumerates every subset. Only practical up to ~20-25 topics. | | Dynamic Programming | `src/knapsack_dp.py` | O(n * W) | Tabulates and backtracks. Scales to hundreds of topics. | Both solvers return the same result `(max_value, selected_topics, total_hours)`, which is what makes it possible to cross-check DP's output against brute force for correctness, then benchmark how each one scales. ## Project structure ``` . ├── src/ │ ├── knapsack_brute_force.py # O(2^n) baseline solver │ ├── knapsack_dp.py # O(n*W) dynamic programming solver │ ├── benchmark.py # Runs both solvers and records time/memory │ └── data/ │ ├── sample_topics_small.csv │ └── sample_topics_large.csv ├── tests/ │ └── test_knapsack.py # Correctness tests (DP vs brute force, edge cases) ├── results/ # Benchmark output (CSV + plots) └── conftest.py ``` ## Requirements - Python 3.10+ - [pytest](https://pypi.org/project/pytest/) (to run the tests) - [matplotlib](https://pypi.org/project/matplotlib/) (to generate benchmark plots) Install dependencies: ```bash pip install pytest matplotlib ``` ## Running the simulation ### 1. Run a single solver on a CSV of topics Each solver can be run directly and takes a `--data` CSV path and a `--capacity` (max study hours): ```bash # Dynamic Programming solver python src/knapsack_dp.py --data src/data/sample_topics_small.csv --capacity 20 # Brute Force solver python src/knapsack_brute_force.py --data src/data/sample_topics_small.csv --capacity 20 ``` Each prints the input topics, the maximum achievable grade boost, and which topics were selected. The topics CSV needs three columns: `topic,hours,value`, for example: ```csv topic,hours,value Data Structures,4,9 Algorithm Complexity,5,10 Dynamic Programming,6,12 ``` > Brute force refuses to run on more than 25 topics by default (2^25+ subsets is not > feasible in pure Python). Use `--force` to override, or just use the DP solver. ### 2. Run the full benchmark `src/benchmark.py` runs both solvers across a range of input sizes, verifies they agree on the answer, and writes results + plots to `results/`: ```bash python src/benchmark.py ``` This runs two sweeps: - **Sweep A** (n = 5 to 20): both solvers, to show brute force's exponential blowup against DP's near-flat runtime, and confirm they agree on the max value. - **Sweep B** (n = 50 to 500): DP only, since brute force is infeasible at this size. Output: - `results/benchmark_results.csv` — raw timing/memory/value data - `results/time_complexity_plot.png` — runtime vs. number of topics - `results/memory_plot.png` — peak memory vs. number of topics ### 3. Run the tests ```bash pytest ``` The test suite (`tests/test_knapsack.py`) checks that DP and brute force agree on random instances and a battery of edge cases (zero capacity, empty topic list, a topic that alone exceeds capacity, etc.). # Algorithm-knapsack