Looking Ahead

In this chapter we looked at the 0/1 knapsack problem as a model problem for dynamic programming. We saw how a naive solution can lead to difficulties when trying to optimize further. These difficulties can be almost impossible to overcome in an interview unless the right approach is taken from the start. We went over the canonical method for solving the 0/1 knapsack problem for both top-down and bottom-up approaches. Finally we extrapolated some of the properties if the 0/1 knapsack problem and used them as heuristics for detecting dynamic programming problems from their description.

In the next chapter, we will go over common variations of the 0/1 knapsack problem. The most obvious one, for example, is the case when values == weights. This is known as the subset sum problem.