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.