0/1 Knapsack Problem Using Dynamic Programming-
Consider:- Knapsack weight capacity = w
- Number of items each having some weight and value = n
Time Complexity- - Each entry of the table requires constant time θ(1) for its computation.
- It takes θ(nw) time to fill (n+1)(w+1) table entries.
- It takes θ(n) time for tracing the solution since tracing process traces the n rows.
- Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic programming.