Understanding the bottom-up solution to the bounded knapsack problem

To solve the bounded knapsack problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom-up solution

When implementing the recurrence relation using a top-down algorithm, i is an index into the weights, values, and counts arrays, and the base case occurs when i drops below 0 or when the remaining capacity reaches 0.

For the recurrence relation, if i < 0 or capacity == 0, the solution is 0, and this serves as the base case.

However, arrays cannot have negative indices and so the base case where i < 0 cannot be handled cleanly. To handle this cleanly in the bottom-up table, we shift the meaning of i so that it represents the number of distinct item types considered rather than an index. This way, the base case becomes i == 0, which maps naturally to row 0 of the table.

How does this shift change the recurrence?

The recurrence relation itself does not change, we still decide how many copies of the last item type under consideration to take (from 0 up to the available count). The only difference is that when i represents the number of item types considered, the last item type of the prefix is at index i - 1 in the weights, values, and counts arrays (instead of index i). This is purely a shift in how we index into the table and the arrays, not a change in logic.

We can use i to denote the number of items considered from the start, instead of the index of the last item.

We create a 2D integer array maxValue of dimensions (n + 1) × (capacity + 1), where maxValue[i][c] stores the maximum value achievable using the first i item types with a capacity of c, respecting the count limits of each item type. All entries are initialized to 0.