7 Knapsack Algorithm
This chapter covers
- Solving the 0/1 Knapsack problem using Dynamic Programming and a 2D matrix
- Defining the 0/1 constraints to manage binary choice mechanics
- Overlapping subproblems and building optimal substructure
In the last few chapters we saw assignment and allocation problems like Gale-Shapley and the Hungarian algorithm. Assignment algorithms taught how to optimize the cost of matching if there are equal numbers of tasks and workers, how preferences dominate the stable matching between proposers and receivers.
Further, string matching algorithms like the Rabin-Karp and Knuth-Morris-Pratt algorithms were discussed to search for and find patterns in long input texts. Every algorithm had its own benefits of fast searching, handling redundancy, and skipping repetitive comparisons.
This chapter talks about an optimization algorithm called the Knapsack algorithm. The knapsack algorithm focuses on maximizing value under a strict constraint of a limit. It introduces a different challenge of choosing what to take and what to leave behind when you cannot have it all.