An Algorithmic Approach to Knapsack Problems
Survey of 0-1, fractional, and multi-dimensional knapsack; implementations of dynamic programming, a scaling FPTAS, and a 1/2-approximate greedy (fractional greedy proved optimal). Python benchmarks for MDKP and baselines; GA and local- search heuristics explored.
Overview
- Surveyed $0–1$, fractional, and multi-dimensional knapsack (MDKP).
- Implemented dynamic programming, a scaling FPTAS, and a $1/2$-approximate greedy; proved fractional greedy is optimal.
- Built Python benchmarks for MDKP and baselines; explored GA and local-search heuristics.