#Trainning & Reference: Data Structures.
- Recursion O(2^n) complexity
- Dynamic O(W*n) complexity
- Memory Function (Recursion + Dynamic) O(W*n - constant) (unimplemented). In general, we cannot expect more than a constant-factor gain in using the memory function method for the knapsack problem, because its time efﬁciency class is the same as that of the bottom-up algorithm. A more signiﬁcant improvement can be expected for dynamic programming algorithms in which a computation of one value takes more than constant time. You should also keep in mind that a memory function algorithm may be less space-efﬁcient than a space-efﬁcient version of a bottom-up algorithm. -- Introduction to the Design and Analysis fo Algorithms 3rd Edition: page 296.
- Source code - Trainning from class.