Understanding the top-down solution to the 0/1 knapsack problem

To solve the 0/1 knapsack problem using a top-down dynamic programming approach, we translate the recurrence relation into a recursive function and use a memoization table to store results of subproblems that have already been solved.

The top down solution

As with any top-down solution, there is a recursive function that solves subproblems and a calling function that initializes the required data structures and triggers the computation. For the 0/1 knapsack, we define a single recursive function knapsack and a calling function that invokes it for the last item and the full capacity.