A comprehensive implementation and performance comparison of various algorithms for solving the 0/1 Knapsack Problem
Demonstrating trade-offs between solution quality, execution time, and memory usage across different algorithmic approaches
The knapsack problem is a classic optimization challenge: select items to maximize value while staying within weight constraints.
This project showcases 4 powerful algorithms with complete performance analysis:
+ 2 EXACT algorithms (guaranteed optimal solutions)
! 2 APPROXIMATE algorithms (fast, good solutions)| Greedy | Dynamic Programming | Branch & Bound | Genetic Algorithm |
|---|---|---|---|
| Lightning Fast | Optimal Solution | Optimal Solution | Large-Scale Solver |
Knapsack/
├── algorithm_comparison_with_items.png # Visualization results
├── branch_and_bound.py # Branch and bound implementation
├── dataset_generator.py # Generates realistic test datasets
├── dynamic_programming.py # DP implementation
├── genetic.py # Genetic algorithm implementation
├── greedy.py # Greedy algorithm implementation
├── knapsack_problem.py # Common dataset loading utilities
├── knapsack_realistic_3000.in # Sample dataset (3000 items)
├── profiling_utils.py # Performance measurement tools
├── test_all.py # Main comparison script
└── readme.md # This file
Prerequisites: Python 3.6+ and matplotlib
Installation & Setup
# Clone the repository
git clone https://github.com/yourusername/Knapsack.git
cd Knapsack
# Install dependencies
pip install matplotlib# Run the complete algorithm comparison
python test_all.pyOptional steps:
# Generate custom dataset (optional - samples included)
python dataset_generator.py| Algorithm | Type | Time Complexity | Space | Optimal? | Speed |
|---|---|---|---|---|---|
| Greedy | Approximate | O(n log n) |
O(1) |
❌ | Fast |
| Dynamic Programming | Exact | O(n × W) |
O(W) |
✅ | Medium |
| Branch & Bound | Exact | O(2^n) |
O(n) |
✅ | Variable |
| Genetic Algorithm | Approximate | O(generations) |
O(population) |
❌ | Medium |
EXACT ALGORITHMS - Click to expand
Dynamic Programming (dynamic_programming.py)
+ Guaranteed optimal solution
+ Handles medium-sized datasets efficiently
+ Well-established, reliable approach
- Memory intensive for large capacities
- Time complexity depends on capacity sizeBest for: Medium datasets where optimality is crucial
Branch and Bound (branch_and_bound.py)
+ Optimal solution guaranteed
+ Can handle large capacities
+ Intelligent pruning reduces search space
+ Memory efficient
- Exponential worst-case time
- Performance varies with data distributionBest for: Large capacity problems requiring optimal solutions
APPROXIMATE ALGORITHMS - Click to expand
Greedy Algorithm (greedy.py)
+ Lightning-fast execution
+ Minimal memory usage
+ Simple implementation
+ Great for real-time applications
- No optimality guarantee
- Quality depends on data characteristicsBest for: When speed matters more than perfect solutions
Genetic Algorithm (genetic.py)
+ Handles massive datasets
+ Consistently good approximations
+ Highly customizable and extensible
+ Robust across different problem types
- No optimality guarantee
- Requires parameter tuning
- Longer execution timeBest for: Very large instances where other methods fail
Performance comparison on 3000-item dataset (W=45544)
Showing execution time, solution quality, and items selected
Performance Metrics - Click to see detailed results
Typical Results on 3000-item Dataset:
- Greedy Algorithm: ~0.01s, Good approximation
- Dynamic Programming: Moderate time, OPTIMAL solution
- Branch and Bound: Variable time, OPTIMAL solution
- Genetic Algorithm: Consistent time, Good approximation
Dataset Format:
<capacity>
<index> <value> <weight>
<index> <value> <weight>
...
Example from knapsack_realistic_3000.in
45544
0 99 82
1 68 88
2 54 85
3 56 93
...
Create your own datasets with generate_realistic_knapsack_dataset:
generate_realistic_knapsack_dataset(
num_items=3000, # Number of items
max_value=100, # Maximum item value
max_weight=100, # Maximum item weight
capacity_ratio=0.3, # Capacity as % of total weight
output_file="custom_dataset.in" # Output filename
)Feel free to extend this project by:
- Implementing additional algorithms (simulated annealing, particle swarm, etc.)
- Adding more sophisticated genetic operators
- Optimizing existing implementations
- Creating new benchmark datasets
- Improving visualizations
This project is licensed under the MIT License. See the LICENSE file for details.
For questions, suggestions, or contributions, please open an issue or submit a pull request on GitHub.