Understanding the top-down solution to the bounded knapsack problem

To solve the bounded 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 bounded 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, values, and counts 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.

Create a function knapsack to return the maximum value achievable from items [0...i] with capacity c, where each item can be used up to counts[i] 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.

The memo array has a size n x (capacity + 1) and is initialized with -1.