From the exercise:
" The knapsack problem is suited for dynamic programming because memoization will allow us to store information instead of making duplicate calls. We will store this information in a two-dimensional array that has a row for every item and
weightCap + 1 number of columns where each element in the 2D array (
matrix ) represents a subproblem. The element at the bottom right will be the optimal solution.
But what exactly do the rows and columns represent? The rows represent the items we have seen. So if we are at row
4 , then we have only seen the first 4 items, meaning the others aren’t being considered yet. The columns represent how much weight the knapsack can hold. If we are at column
7 , then we are looking at a subset of the larger problem where our knapsack has a weight capacity of
7 . The number stored inside
matrix is the maximum value we can take given the weight capacity and number of items we have seen for that subproblem. By the time we get to the bottom right space in
matrix , we have considered every possible subproblem and taken the maximum possible value."
- What does the final matrix look like?
- why are we using weightcap + 1 number of columns? We only look at one particular weightcap right?
- Why is the optimal solution in the bottom right?