Understanding the bottom-up solution to the unbounded knapsack problem

To solve the unbounded 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.