Understanding the top-down solution to the unbounded knapsack problem

To solve the unbounded 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 unbounded knapsack, we define a single recursive function knapsack and a calling function that invokes it for the last item and the full capacity.

The knapsack function

The function knapsack() takes as input an index i into the items, the remaining capacity c, references to the weights and values arrays, and a reference to the memoization array memo. The function returns the maximum value achievable using items 0 through i with the given remaining capacity c, where each item can be used an unlimited number of times.

The memo array has dimensions n × (capacity + 1) where n is the number of distinct items and capacity is the total knapsack capacity, and is initialized with -1 in the calling function, where -1 indicates that the state has not yet been computed. Any non-negative value represents the computed maximum achievable value for that state.