Need some help with the knapsack functional programming solution in javascript

[system7514817679]

Hi Everyone, I am currently working on the knapsack functional programming solution, and I find it difficult to understand (https://www.codecademy.com/paths/pass-the-technical-interview-with-javascript/tracks/javascript-interview-prep-and-algorithm-practice/modules/javascript-algorithm-practice/articles/the-knapsack-problem).

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."

my questions:

• 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?

[system7514817679]

cc @didash perhaps you can have a look at it?

[didash]

Hi once again, @system7514817679, and my apologies for the late response.

And sorry for being so repetitive here, referring to the topic you made earlier (Two pointer solution to rainwater capture needs some explaining), remember that sometimes to understand better code that has been provided to you, one must have to ‘reverse engineer’ it.

And just like @realkennylin said, in his post on that topic:

@realkennylin

The one thing I would add that’s helped me understand how “reverse engineering” a solution works is to add in console.log() statements where I’m not sure what’s happening.

So if you would like to see how the final matrix looks like. Copy the code from the solution to any text editor and just use console.log() to visualize any variable you are curious about. If the output is too complex, try maybe using other inputs. Such as the first example that is being provided to you in the article you shared:

weightCap = 5 
weights = [1, 3, 5]
values = [250, 300, 500]

Changing the inputs a couple of times and checking how the code works can reinforce that you have understood the code’s methodology.

---

Your other two questions are actually answered in the quote from the article that you provided. We just have to analyze it a bit further.

Why are we using weightcap + 1 number of columns?

(…) 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. (…)

(…) Likewise, every element in the zeroeth column represents a subproblem where our knapsack has a capacity of 0, giving us no value to take. Because of this, we start by filling the zeroeth row and column with 0. (…)

So if every column represents the weight that the knapsack can carry, starting from 0, then we will need a weightCap + 1 length array to fill all the spots. In other words, we want to know which items fill in the whole knapsack, but to do so we need to check how many items (alone or in a bundle) have a weight of 0, then 1, then 2, 3, 4, … and so on until we reach the knapsack full capacity. And since we start from 0, until we get to weightCap , we will have to make a total of weightCap + 1 tests.

(Also there is a “numItems + 1” number of rows, as we start from 0 to the total of items. But, for some reason, the article doesn’t mention this. To corroborate this information check the matrix generated)

Why is the optimal solution in the bottom right?

(…) The rows represent the items we have seen. (…) The columns represent how much weight the knapsack can hold. (…) By the time we get to the bottom right space in matrix, we have considered every possible subproblem and taken the maximum possible value."

So the only way to know the optimal solution for the problem is to consider all of the items (only able at the last row), and that the knapsack is full (last column).

---

Don’t forget that if you are still having problems please reply to this post, I will be always glad to help you in any way I can.

Happy coding !