FOR THE solution of the Knapsack 0/1 problem, there is an error in the verbal description of the answer. You have:
" The function knapSack
makes a lookupTable
within the function that stores the maximum value that can be attained with maximum capacity (lines 29-35 ). This function calls the helper function knapsackRecursive
(line 36 ). It returns the maximum value that can be attained using only the first i
items, i.e., items at the currentIndex
while keeping their total weight no more than weights
."
The error is in the line “It returns the maximum value that can be attained using only the first i
items.”
This is incorrect. “knapsackRecursive” returns the maximum value that can be attained using the LAST profitsLength - i
items. This is because, as i
increments, the “knapsackRecursive” returns the maximum value that can be attained by the subarray starting at i
until the END of the array.
If the description is unclear or wrong (as in this case) it creates confusion which obstructs the learning process. Please correct! Thank you!
Nilay
Course: https://www.educative.io/collection/10370001/5347133077061632
Lesson: https://www.educative.io/collection/page/10370001/5347133077061632/4749983322472448