engineering recuitment GATE CSE 2023-24 Test Series Algorithms Algorithm Design Techniques Dynamic Programming
Read the following statements about 0/1 Knapsack problem.
Note:
Where n is the number of items and W is the weight of the Knapsack .
Which of the following statements are true?
1
Time complexity of Knapsack is O(n* W) where W is the weight of the Knapsack and there are n items.
2
Time complexity of Knapsack is min( O(n*W) , O(2^n) ) where W is the weight of the Knapsack and there are n items.
3
Knapsack can be implemented in O(n*W) space .
4
Knapsack can be implemented in O(W) space.