Understanding the bottom-up solution to the 0/1 knapsack problem

To solve the 0/1 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 and values 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 items 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 whether to include or exclude the last item under consideration. The only difference is that when i represents the number of items considered, the last item of the prefix is at index i - 1 in the weights and values 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 items with a capacity of c. All entries are initialized to 0.