To determinebase_case determine the smallest valid input.
For knapsack if either the items is 0 or the weight is 0 then output will be 0. So this is the base case.
In Recursion it always needs to be called with smaller input so recursion can exit else it will keep calling itself. To apply above in knapsack keep reducing size of array as iterating through the array, if the weight gets filled then exit.
Two choice, when including the equation is going to reduce the weight in the recursive function so w - wt[n-1]
The martix has to be created for variables that are changing. Here they are n + 1 and w + 1
choice_diagram really made it easy to write above equation.
Output should be sum of profits or maximum profit.
To domemoization of above first identify where all recursive function is present,
In the above three recursive function only two variables are changing, we will keep matrix of these two
After thebase_case add the condition to check if value exists in the t matrix, if it exists then return it.
Second change, before returning store the value in t matrix,
In Recursion instead of initialising values with -1 can we keep them empty and check for undefined or null to see if value exists? This behaviour may be different language wise, it should be fine in Javascript.
Bottom_Up or Tabulation approach the matrix size will be = bag weight * number of items.
The first row and first column have to be initialised,
base_case will turn into initialisation for the matrix, the initial row and column are going to be 0 becausebase_case tells that if weight is 0 or n is 0 then return 0. If it would have been -1 then we would have set -1.
Code for initializing here
let t = [];for (let i = 0; i < n + 1; i++) { for (let j = 0; j < w + 1; j++) { if (i == 0 || j == 0) { t[i][j] = 0; } }}
Recursive to tabulation
Q. How will the recursive program change if the output should be the weight and value of all items instead of just the sum of weight/ value of the selected items.
Problem is broken down tobase_case andchoice_diagram
