Read the following statements about 0/1 Knapsack problem.
(i) Time complexity of Knapsack is O(n* W) where W is the weight of the Knapsack and there are n items.
(ii) 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.
(iii) Knapsack can be implemented in O(n*W) space .
(iv) Knapsack can be implemented in O(W) space.
where n is the number of items and W is the weight of the Knapsack .
Mark the correct option
- (i) and (iii) is true
- (ii) and (iii) is true
- (i) ( iii) (iv) is true
- (ii) (iii) (iv) is true.